UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215066#2410. 图案naroto202201ms1128kbC++1.5kb2024-11-25 22:21:382024-11-25 23:12:43

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MN=1e6+5;
ll n,k;
char c[MN];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
char gc(){char ch=getchar();while(ch<'a'||ch>'z')ch=getchar();return ch;}
ll check(ll p){
    if(k==1) return 1;
    if(p<k) return 0;
    if(p%k==0){
        ll num=p/k;bool flag=true;
        for(int i=1; i<=num; i++){
            for(int j=i+num; j<=p; j+=num) if(c[j]!=c[j-num]){
                flag=false;
                break;
            }
            if(!flag) break;
        }
        if(flag) return 1;
    }
    for(int b=1; b<p; b++) if((p-b)%k==0){
        ll a=(p-b)/k-b,num=k*(a+b);bool flag=true;
        if(a<0) break;
        for(int i=1; i<=num; i+=a+b){
            for(int j=1; j<=b; j++) if(c[i+j-1]!=c[num+j]){
                flag=false;
                break;
            }
            if(!flag) break;
        }
        if(!flag) continue;
        for(int i=1; i<=a; i++) for(int j=i+2*b+a; i<=p; i+=a+b) if(c[j]!=c[j-a-b]){
            flag=false;
            break;
        }
        if(flag) return 1;
    }
    return 0;
}
int main(){
    n=read();k=read();for(int i=1; i<=n; i++) c[i]=gc();
    for(int i=1; i<=n; i++) write(check(i));
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1124kb

input:

100 2
xxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwxxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwex...

output:

0100010000000100000000000000011111111111111110000010000000000000000000000000000010000000000100000000

result:

wrong answer 1st lines differ - expected: '010001000000010000000000000001...000000000000000000000010...

Subtask #2:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 0ms
memory: 1128kb

input:

100 2
xxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwxxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwex...

output:

0100010000000100000000000000011111111111111110000010000000000000000000000000000010000000000100000000

result:

wrong answer 1st lines differ - expected: '010001000000010000000000000001...000000000000000000000010...

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: 0
Wrong Answer
time: 1ms
memory: 1128kb

input:

100 2
xxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwxxyxxyyxxyxxyypxxyxxyyxxyxxyypxxyxxyyxxyxxyypwex...

output:

0100010000000100000000000000011111111111111110000010000000000000000000000000000010000000000100000000

result:

wrong answer 1st lines differ - expected: '010001000000010000000000000001...000000000000000000000010...