QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #121593 | #2106. Druk | LFCode | 100 ✓ | 60ms | 3480kb | C++14 | 2.2kb | 2023-07-08 15:08:58 | 2023-07-08 15:09:01 |
Judging History
answer
#include<cstdio>
const int N=1010;
int n,m,cnt,ac,q[N],ans[N];
char a[N][N],b[N];
bool ck[N][N],flag=true;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
char gc(){char ch=getchar();while(ch<'a'||ch>'z')ch=getchar();return ch;}
bool check1(int x){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ck[i][j]=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ck[i][j])continue;
if(i+x-1<=n){
bool pd=true;
for(int k=0;k<x;k++)if(a[i+k][j]!=b[k+1]||ck[i+k][j]){pd=false;break;}
if(pd)for(int k=0;k<x;k++)ck[i+k][j]=true;
}
if(ck[i][j])continue;
if(j+x-1<=m){
bool pd=true;
for(int k=0;k<x;k++)if(a[i][j+k]!=b[k+1]||ck[i][j+k]){pd=false;break;}
if(pd)for(int k=0;k<x;k++)ck[i][j+k]=true;
}
if(!ck[i][j])return false;
}
return true;
}
bool check2(int x){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ck[i][j]=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ck[i][j])continue;
if(j+x-1<=m){
bool pd=true;
for(int k=0;k<x;k++)if(a[i][j+k]!=b[k+1]||ck[i][j+k]){pd=false;break;}
if(pd)for(int k=0;k<x;k++)ck[i][j+k]=true;
}
if(ck[i][j])continue;
if(i+x-1<=n){
bool pd=true;
for(int k=0;k<x;k++)if(a[i+k][j]!=b[k+1]||ck[i+k][j]){pd=false;break;}
if(pd)for(int k=0;k<x;k++)ck[i+k][j]=true;
}
if(!ck[i][j])return false;
}
return true;
}
int main(){
n=read();m=read();
for(int i=1;i<=Max(n,m);i++)if(n%i==0||m%i==0)q[++cnt]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
a[i][j]=gc();
if(a[i][j]!=a[1][1])flag=false;
}
if(flag){
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)printf("%d ",q[i]);
return 0;
}
for(int i=1;i<=cnt;i++){
int np=q[i];
if(np<=n){
for(int j=1;j<=np;j++)b[j]=a[j][1];
if(check1(np)||check2(np))ans[++ac]=np;
}
if(np<=m&&ans[ac]!=np){
for(int j=1;j<=np;j++)b[j]=a[1][j];
if(check1(np)||check2(np))ans[++ac]=np;
}
}
printf("%d\n",ac);
for(int i=1;i<=ac;i++)printf("%d ",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 0ms
memory: 1488kb
input:
1 1000 ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
12 2 4 8 10 20 40 50 100 200 250 500 1000
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 1488kb
input:
1 720 yddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyyd...
output:
1 720
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 1704kb
input:
1 810 prprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprpprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprpprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprpprprprprprprprprprprprprprprprprprprprprprprprprprp...
output:
4 81 162 405 810
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 1508kb
input:
1 888 jwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnr...
output:
8 37 74 111 148 222 296 444 888
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 1744kb
input:
1 864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
24 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 72 96 108 144 216 288 432 864
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 1524kb
input:
1 1000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16 1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000
result:
ok 2 lines
Subtask #2:
score: 25
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 25
Accepted
time: 0ms
memory: 1504kb
input:
3 1000 ababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaaba...
output:
9 10 20 40 50 100 200 250 500 1000
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 1488kb
input:
3 900 ahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhz...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 1520kb
input:
2 1000 abaabaaaaaaaaabaaabaabaabaaaaaaababaaabaaaabaaaaaaaabaaababaababaaaaabaaabaaabaabaababaabaaaabaaaababaabaaaaaaaaaababaababaaabaaababaaaabaabaabaabababaaabaababaabaaabaaababaababaababaababaaaaaaaaaaaaaabababaaaaaaabaaaababaabababaaaabaaabaabaaaabaabaababaabaaaaaaaabaaaaaaaaaaaaaaaaaaababaaabaa...
output:
1 2
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 1500kb
input:
3 1000 klklklkklkklklklklklklklklklklklklkkkklklklkklklklkkkklkklklkklkklkklkkklkklkkklklklklklklklklkklklklklkklklklklklklklklklkklklklklkklklkkklklkkklklklklklklklklkklkklklklklklklklklklkkklklklkkklklklkklklklkkkklkkkkklklklklklklklkklklklkklklkklklklklklkkkkkklklklkkklkkklklklklklklklklklklklklk...
output:
1 2
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 1496kb
input:
3 1000 ooopopopopoopooopopooopopopoopopopooooooopopopoooopoopopopoopopooopopooopoooopopopopopopopopoopopopoopooopopopopopopopopopopopopopopopopopopoopopooopoopopopopopopopopopopopopopopopoooooopoopopoopopoooopopopopoopopopopopopopopoopoooopoopopoooopopooopopopopopooopopoopopopopopoopopoopopopopopopo...
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 1740kb
input:
3 1000 ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
12 2 4 8 10 20 40 50 100 200 250 500 1000
result:
ok 2 lines
Subtask #3:
score: 20
Accepted
Test #13:
score: 20
Accepted
time: 0ms
memory: 1748kb
input:
20 20 eeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eegeeeeeegeeeeeeeeee eeeeeeeeeeegeeeeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeegeeeeeeeeege eeeeeeeeeeeeeegeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eeegeeegeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeegeeeee eeeeggeeeeeeeeeeeeee eeeeeeeeeeeeeeegeege ...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 1508kb
input:
3 8 ababaaba babaabab abaababa
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 0ms
memory: 1516kb
input:
18 15 aabaaaabaabaaba aabaaaabaaabaaa aabbbaaaaaaaaab aaabaaaabaaabba aaababbbabbbaaa baaabaaaaaaaaab aaaaaaaabaaabba abbbabbbabbbaaa baaabaaaaaaaaab aaaaaaaabaaabba abbbabbbabbbaaa baabbaabaaabaab aaabaaabbaaabba aaaaaaabaaaaaaa baaabaaaabbbaab abbbaaaabaabbba aaababbbaabaaba baabbaabaabaabb
output:
1 3
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 1548kb
input:
14 15 abababaabababaa abababaaaaaaaab aaaaaaabbbbbbba bbbbbbbaaaaaaab aaaaaaabbbbbbba bbbbbbbaaaaaaab aaaaaaabbbbbbba bbbbbbbaaaaaaaa aaaaaaaabababab abababaabababaa abababaabababab abababaabababaa abababaabababab abababaabababaa
output:
1 7
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 1552kb
input:
4 9 aabaaabaa babababab aabaaabaa abaabaaba
output:
1 3
result:
ok 2 lines
Subtask #4:
score: 45
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #18:
score: 45
Accepted
time: 2ms
memory: 1980kb
input:
512 729 pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
16 1 2 3 4 8 9 16 27 32 64 81 128 243 256 512 729
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 4ms
memory: 2244kb
input:
800 918 kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...
output:
32 1 2 3 4 5 6 8 9 10 16 17 18 20 25 27 32 34 40 50 51 54 80 100 102 153 160 200 306 400 459 800 918
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 5ms
memory: 2376kb
input:
924 871 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
27 1 2 3 4 6 7 11 12 13 14 21 22 28 33 42 44 66 67 77 84 132 154 231 308 462 871 924
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 0ms
memory: 1640kb
input:
62 48 abaabaabaabaaabaabaabaabaaabaabaabaabaaaaaaaaaaa abaabaabaabababaabaabaababaaaaaaaaaaaabbbbbbbbbb abaabaabaabaaabaabaabaabaabbbbbbbbbbbbaaaaaaaaaa abaabaabaabaaabaabaabaabaaaaaaaaaaaaaaaaaaaaaaaa abaabaabaabababaabaabaababaaaaaaaaaaaabbbbbbbbbb aaaaaaaaaaaaaabaabaabaabaabbbbbbbbbbbbaaaaaaaaaa ...
output:
3 3 6 12
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 60ms
memory: 3480kb
input:
1000 1000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 8ms
memory: 2652kb
input:
600 900 abacabacabacaaaabacabacabacaaaaabacabacabacabacabacabacaaaaaaabacabacabacabacabacabacaaaaaabacabacabacabacabacabacaaaaaaabacabacabacaaabacabacabacaaaaabacabacabacabacabacabacaaaaaaaabacabacabacaaaabacabacabacaaabacabacabacaaabacabacabacaaaaaabacabacabacabacabacabacaaaaaaabacabacabacabacabaca...
output:
2 4 12
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 12ms
memory: 3456kb
input:
1000 1000 ababababaaaababababaaababababaaaaaaaaaaaaababababaaaababababaababababaababababaaaababababababababaaaaababababababababaaaababababaaababababaaababababaaaababababaaababababababababaaaaababababababababaaaababababaababababaaaaaababababaaababababaababababababababaaaababababababababaaaaaababababa...
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 20ms
memory: 3352kb
input:
960 1000 aababababababababababababaaaaaaaaaaaaaaaaaaaaaaaaaababababababababababababababababababababababababaaaaaababababababababababababaaaaaaaaaaaaaaaaaaaaaaaaaaababababababababababababaaaaaaaaaaaaaaaaaaaaaaaababababababababababababababababababababababababaaababababababababababababaaabababababababa...
output:
6 2 4 6 8 12 24
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 11ms
memory: 3460kb
input:
984 984 ababababababababababababaaaababababababababababababaaaaaaaaaaaaababababababababababababaababababababababababababaaaaaaaaaaaaaaaaababababababababababababababababababababababababaaaaaaaaaaaaaababababababababababababababababababababababababaaaaaaaaaaaaaaaaabababababababababababababababababababa...
output:
2 2 6
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 6ms
memory: 2864kb
input:
700 800 aabaaabaabababaabaaabaabaaaabaaaaaaaaaaaaaaaabaaabaaaaaaaaaabaaabababababaaaaaaaabaaabaaabababaabaaabaabababaaaaaaaaaaaaaaabaaababababababaaabababababaaaaaaaaaaabaaababababababaaabaaaaaaaaaaaaaaaaaaaaaabaaababababababaaabababababaaaaaaaaaaaaabaaabaaaaaaababaaabababababaaaaaaaaaaaabaaabaababa...
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 10ms
memory: 3444kb
input:
1000 1000 abbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaab...
output:
1 4
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed