ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215015 | #2410. 图案 | ThySecret | 0 | 3ms | 1180kb | C++11 | 2.0kb | 2024-11-25 19:57:16 | 2024-11-25 23:06:41 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
const int base = 131;
template<typename Type>
inline void read(Type &res)
{
res = 0;
int ch = getchar(), flag = 0;
while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }
int n, k;
int kmp[N];
char str[N];
// ULL hsh[N], fc[N];
// inline ULL gethash(int l, int r) { return hsh[r] - hsh[l - 1] * fc[r - l + 1]; }
bool check(int idx)
{
// for (int cur = kmp[idx]; cur; cur = kmp[cur])
int cur = idx;
do
{
cur = kmp[cur];
int rest = idx - (k + 1) * cur;
if (rest < 0 || rest % k != 0) continue;
int lgst = kmp[idx - cur];
if (!lgst) continue;
if ((idx - cur) % (idx - cur - lgst) == 0 && ((idx - cur) / (idx - cur - lgst)) % k == 0) return true;
} while (cur != 0);
return false;
}
signed main()
{
// for (int i = fc[0] = 1; i < N; i ++) fc[i] = fc[i - 1] * base;
scanf("%lld%lld%s", &n, &k, str + 1);
// for (int i = 1; i <= n; i ++)
// hsh[i] = hsh[i - 1] * base + str[i];
for (int i = 2, j = 0; i <= n; i ++)
{
while (j && str[i] != str[j + 1]) j = kmp[j];
if (str[i] == str[j + 1]) j ++;
kmp[i] = j;
}
for (int i = 1; i <= n; i ++)
putchar(check(i) ^ 48);
putchar(10);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 0ms
memory: 1176kb
input:
100 2 xxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwxxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwex...
output:
0100010000000100000000000000011111111111111110000000000000000000000000000000000000000000000100000000
result:
ok single line: '010001000000010000000000000001...0000000000000000000000100000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 3 xxxyxxxyxxxyyxxxyxxxyxxxyyxxxyxxxyxxxyypxxxyxxxyxxxyyxxxyxxxyxxxyyxxxyxxxyxxxyypxxxyxxxyxxxyyx...
output:
0010000000010000000000000000000000000010000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '001000000001000000000000000000...0000000000000000000000000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 2 baaaabbbaaabaabaaababbabaabbbabaaaabbababaaaabbaabbaaaababbaaabaaaaabbbbbaaaaabbbbbbaaabbaabaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 3 baaaabbbaaabaabaaababbabaabbbabaaaabbababaaaabbaabbaaaababbaaabaaaaabbbbbaaaaabbbbbbaaabbaabaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 15 xxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxx...
output:
0000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000001000000000000000...0000000000000000000000000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 20 xxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxx...
output:
0000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000010000000000...0000000000000000000000000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 7 xxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxx...
output:
0000001000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000
result:
ok single line: '000000100000000000000000000000...0000000000000000000000000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 4 babbababaabababaabbaaabbbaaaaabaaababbbbaaaaabbbaabbbbaaabbbbabbaaaaaabababaabaababbbbabbbbbaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 5 kkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxskkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxskkkkkkxk...
output:
0000110000000000000000000000000000111111110000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000011000000000000000000000000...0000000000000000000000000000000'
Test #10:
score: -20
Wrong Answer
time: 0ms
memory: 1180kb
input:
100 1 ggggvggggvoggggvggggvoggggvggggvocggggvggggvoggggvggggvoggggvggggvocjggggvggggvoggggvggggvoggg...
output:
0111000001000000000001111111111110000000000000000000000000000000000100000000000000000000000000000000
result:
wrong answer 1st lines differ - expected: '111111111111111111111111111111...111111111111111111111111...
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 20
Accepted
time: 0ms
memory: 1176kb
input:
100 2 xxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwxxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwex...
output:
0100010000000100000000000000011111111111111110000000000000000000000000000000000000000000000100000000
result:
ok single line: '010001000000010000000000000001...0000000000000000000000100000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 1180kb
input:
100 3 xxxyxxxyxxxyyxxxyxxxyxxxyyxxxyxxxyxxxyypxxxyxxxyxxxyyxxxyxxxyxxxyyxxxyxxxyxxxyypxxxyxxxyxxxyyx...
output:
0010000000010000000000000000000000000010000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '001000000001000000000000000000...0000000000000000000000000000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 2 baaaabbbaaabaabaaababbabaabbbabaaaabbababaaaabbaabbaaaababbaaabaaaaabbbbbaaaaabbbbbbaaabbaabaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 3 baaaabbbaaabaabaaababbabaabbbabaaaabbababaaaabbaabbaaaababbaaabaaaaabbbbbaaaaabbbbbbaaabbaabaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 1180kb
input:
100 15 xxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxx...
output:
0000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000001000000000000000...0000000000000000000000000000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 20 xxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxx...
output:
0000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000010000000000...0000000000000000000000000000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 7 xxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxx...
output:
0000001000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000
result:
ok single line: '000000100000000000000000000000...0000000000000000000000000000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 4 babbababaabababaabbaaabbbaaaaabaaababbbbaaaaabbbaabbbbaaabbbbabbaaaaaabababaabaababbbbabbbbbaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 5 kkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxskkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxskkkkkkxk...
output:
0000110000000000000000000000000000111111110000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000011000000000000000000000000...0000000000000000000000000000000'
Test #23:
score: -20
Wrong Answer
time: 0ms
memory: 1180kb
input:
100 1 ggggvggggvoggggvggggvoggggvggggvocggggvggggvoggggvggggvoggggvggggvocjggggvggggvoggggvggggvoggg...
output:
0111000001000000000001111111111110000000000000000000000000000000000100000000000000000000000000000000
result:
wrong answer 1st lines differ - expected: '111111111111111111111111111111...111111111111111111111111...
Subtask #3:
score: 0
Time Limit Exceeded
Test #51:
score: 0
Time Limit Exceeded
input:
1000000 23 cicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicicic...
output:
0000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000111110000...
result:
Subtask #4:
score: 0
Wrong Answer
Test #57:
score: 40
Accepted
time: 0ms
memory: 1180kb
input:
100 2 xxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwxxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwex...
output:
0100010000000100000000000000011111111111111110000000000000000000000000000000000000000000000100000000
result:
ok single line: '010001000000010000000000000001...0000000000000000000000100000000'
Test #58:
score: 0
Accepted
time: 1ms
memory: 1180kb
input:
100 3 xxxyxxxyxxxyyxxxyxxxyxxxyyxxxyxxxyxxxyypxxxyxxxyxxxyyxxxyxxxyxxxyyxxxyxxxyxxxyypxxxyxxxyxxxyyx...
output:
0010000000010000000000000000000000000010000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '001000000001000000000000000000...0000000000000000000000000000000'
Test #59:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 2 baaaabbbaaabaabaaababbabaabbbabaaaabbababaaaabbaabbaaaababbaaabaaaaabbbbbaaaaabbbbbbaaabbaabaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #60:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 3 baaaabbbaaabaabaaababbabaabbbabaaaabbababaaaabbaabbaaaababbaaabaaaaabbbbbaaaaabbbbbbaaabbaabaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #61:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 15 xxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxyxxxxxxxxxxxxx...
output:
0000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000001000000000000000...0000000000000000000000000000000'
Test #62:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 20 xxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxxxxxxxxxxxxxyxxxxxxxxx...
output:
0000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000010000000000...0000000000000000000000000000000'
Test #63:
score: 0
Accepted
time: 0ms
memory: 1180kb
input:
100 7 xxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyyxxxxxxxyxxxxxxxyxxxxxxxyxxxxxxxyxxxxx...
output:
0000001000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000
result:
ok single line: '000000100000000000000000000000...0000000000000000000000000000000'
Test #64:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 4 babbababaabababaabbaaabbbaaaaabaaababbbbaaaaabbbaabbbbaaabbbbabbaaaaaabababaabaababbbbabbbbbaa...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #65:
score: 0
Accepted
time: 0ms
memory: 1176kb
input:
100 5 kkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxskkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxkkkkkkxskkkkkkxk...
output:
0000110000000000000000000000000000111111110000000000000000000000000000000000000000000000000000000000
result:
ok single line: '000011000000000000000000000000...0000000000000000000000000000000'
Test #66:
score: -40
Wrong Answer
time: 0ms
memory: 1180kb
input:
100 1 ggggvggggvoggggvggggvoggggvggggvocggggvggggvoggggvggggvoggggvggggvocjggggvggggvoggggvggggvoggg...
output:
0111000001000000000001111111111110000000000000000000000000000000000100000000000000000000000000000000
result:
wrong answer 1st lines differ - expected: '111111111111111111111111111111...111111111111111111111111...