UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215015#2410. 图案ThySecret03ms1180kbC++112.0kb2024-11-25 19:57:162024-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...