QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#903940 | #7399. Balanced Binary String | cz_yxx | WA | 17ms | 3840kb | C++20 | 1.5kb | 2025-02-17 19:56:56 | 2025-02-17 19:56:57 |
Judging History
answer
// sis puella oier
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
ll read(){
ll xx = 0, f = 1; char ch = getchar();
for (;!isdigit(ch); ch = getchar())f = (ch == '-' ? -1 : 1);
for (; isdigit(ch); ch = getchar())xx = (xx << 3) + (xx << 1) + ch - '0';
return xx * f;
}
const int N = 1030;
char s[N];
int n, f[N], g[N];
int gcd(int x, int y){return y == 0 ? x : gcd(y, x % y);}
bool chk1(){for (int i = 1; i <= n; ++i)if (s[i] != '?')return 0; return 1;}
bool chk0(){for (int i = 1; i <= n; ++i)if (s[i] == '1')return 0; return 1;}
char a[N];
bitset <N << 1> tmp, ff[2], fl;
void solve(){
scanf("%s", s + 1), n = strlen(s + 1);
if (chk1()){printf("%d\n", f[n] + 1); return ;}
int ans = 0;
for (int i = 1; i <= n; ++i){
tmp.reset();
for (int j = 0; j < i; ++j)tmp[n * j / i + 1] = 1;
ff[0].reset(), ff[1].reset();
for (int j = 1; j <= n; ++j)ff[tmp[j]][j] = ff[tmp[j]][j + n] = 1;
int dd = n / gcd(i, n);
fl.set();
for (int j = 1; j <= n; ++j)if (s[j] != '?')fl &= ff[s[j]-'0'] >> (j-1);
for (int j = 1; j <= dd; ++j)if (fl[j])++ans;
}
// cout<<ans<<endl;
ans += chk0(); printf("%d\n", ans);
// exit(0);
}
signed main(){
//freopen("count.in", "r", stdin);
//freopen("count.out", "w", stdout);
for (int i = 1; i <= 1000; ++i)
for (int j = 1; j <= i; ++j)f[i] += i / gcd(i, j);
int _ = read(); while(_--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 14ms
memory: 3840kb
input:
10 ? ?? ??1 ???0 ????1 ?????0 ??????1 ???????0 ????????1 ?????????0
output:
2 4 4 6 11 11 22 22 31 32
result:
ok 10 tokens
Test #2:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
1024 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0 1 ? 0...
output:
1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 ...
result:
ok 1024 tokens
Test #3:
score: 0
Accepted
time: 12ms
memory: 3840kb
input:
512 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ?? 00 10 ?0 01 11 ?1 0? 1? ??...
output:
1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 ...
result:
ok 512 tokens
Test #4:
score: 0
Accepted
time: 14ms
memory: 3712kb
input:
341 000 100 ?00 010 110 ?10 0?0 1?0 ??0 001 101 ?01 011 111 ?11 0?1 1?1 ??1 00? 10? ?0? 01? 11? ?1? 0?? 1?? ??? 000 100 ?00 010 110 ?10 0?0 1?0 ??0 001 101 ?01 011 111 ?11 0?1 1?1 ??1 00? 10? ?0? 01? 11? ?1? 0?? 1?? ??? 000 100 ?00 010 110 ?10 0?0 1?0 ??0 001 101 ?01 011 111 ?11 0?1 1?1 ??1 00? 10? ...
output:
1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 2 2 4 2 2 4 4 4 8 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 2 2 4 2 2 4 4 4 8 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 2 2 4 2 2 4 4 4 8 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 2 2 4 2 2 4 4 4 8 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 2 2 4 2 2 4 2 2 4 4 4 8 1 1 2 1 1 2 2 2 4 1 1 2 1 1 2 ...
result:
ok 341 tokens
Test #5:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
256 0000 1000 ?000 0100 1100 ?100 0?00 1?00 ??00 0010 1010 ?010 0110 1110 ?110 0?10 1?10 ??10 00?0 10?0 ?0?0 01?0 11?0 ?1?0 0??0 1??0 ???0 0001 1001 ?001 0101 1101 ?101 0?01 1?01 ??01 0011 1011 ?011 0111 1111 ?111 0?11 1?11 ??11 00?1 10?1 ?0?1 01?1 11?1 ?1?1 0??1 1??1 ???1 000? 100? ?00? 010? 110? ?...
output:
1 1 2 1 0 1 2 1 3 1 1 2 0 1 1 1 2 3 2 2 4 1 1 2 3 3 6 1 0 1 1 1 2 2 1 3 0 1 1 1 1 2 1 2 3 1 1 2 2 2 4 3 3 6 2 1 3 2 1 3 4 2 6 1 2 3 1 2 3 2 4 6 3 3 6 3 3 6 6 6 12 1 1 2 1 0 1 2 1 3 1 1 2 0 1 1 1 2 3 2 2 4 1 1 2 3 3 6 1 0 1 1 1 2 2 1 3 0 1 1 1 1 2 1 2 3 1 1 2 2 2 4 3 3 6 2 1 3 2 1 3 4 2 6 1 2 3 1 2 3...
result:
ok 256 tokens
Test #6:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
204 1?001 11?10 0?1?1 0?0?1 110?1 0??00 ?10?1 ?0?01 ??011 1001? 11??0 00001 10??? 0?110 1?101 0?1?? 00101 ?011? ????1 ?0101 1??01 10010 ?1010 01011 000?? 1000? 011?? ?0110 10111 110?1 00?01 ??101 10010 00001 ?0?0? 01111 10110 1?0?0 0101? 1?010 11111 11111 ???00 001?? ???01 0?1?? 10110 ?0?10 ??1?? 00...
output:
0 2 3 3 1 3 3 3 2 1 2 1 6 0 2 4 1 2 11 2 2 1 2 1 3 1 2 1 1 1 2 4 1 1 7 1 1 3 2 2 1 1 5 2 6 4 1 3 11 4 11 0 1 1 3 4 2 1 4 2 6 11 1 5 2 3 2 2 1 1 3 4 2 4 7 2 2 2 2 2 1 6 3 2 2 2 1 2 2 6 1 3 3 2 11 4 2 1 3 11 1 11 1 6 4 1 2 6 4 1 7 11 2 1 4 2 3 0 3 3 1 2 0 1 2 3 3 7 6 2 2 4 2 1 2 1 1 5 5 4 3 1 7 0 3 1 ...
result:
ok 204 tokens
Test #7:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
170 ?01??0 00?10? ????0? 1?0?00 ?1?110 101000 1?0?1? 010?01 00010? 100?01 01?101 111100 ??0?1? 1?11?0 00?111 01?110 00?10? 101101 0?01?1 01?101 0?1100 00110? ?10??? ?000?? ?1?10? 01?111 01?101 1???1? 0000?1 01??11 ?10?1? 10?0?? ?1010? 010110 0111?? 1??0?1 1??100 010011 11?001 01??11 01??01 ?000?1 11...
output:
2 1 11 2 2 0 2 1 1 0 1 0 4 1 0 0 1 1 1 1 0 0 5 4 2 1 1 7 1 2 3 2 1 0 1 1 1 0 0 2 1 1 1 1 3 1 2 1 0 4 5 11 5 1 1 2 11 1 1 1 0 1 2 1 0 3 1 5 2 0 0 1 1 1 11 2 0 0 2 3 2 1 1 1 0 1 2 3 4 0 1 2 2 1 1 0 3 0 3 0 2 2 3 1 1 1 1 1 3 1 5 1 0 1 1 0 4 2 1 2 0 0 2 2 2 1 2 8 0 0 0 3 1 1 2 1 1 6 1 3 0 2 11 2 0 3 0 2...
result:
ok 170 tokens
Test #8:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
146 1010001 1100010 11001?1 001??11 101?011 0??1011 ?111??0 1110011 10?0?0? 11?10?0 ??11??? ??1?00? 0??1000 ??01??1 1101?00 0?01?11 0001??? ?001?0? ??011?0 ?010?0? 0011001 0??1?11 11011?0 0?001?1 10?110? ?11011? 1110101 ??1?10? 11??0?0 0110?00 1?11101 ??1?10? 1010100 ?10?11? ?101010 ?000100 ?0001?? ...
output:
0 0 0 0 1 2 1 0 4 1 10 2 1 6 0 1 2 3 1 5 0 3 1 1 1 3 0 6 1 0 2 6 1 2 2 2 2 4 0 10 2 4 3 6 4 6 0 3 0 0 3 2 1 3 0 1 0 0 4 0 1 3 3 0 0 0 0 14 4 6 5 8 0 4 2 1 1 1 5 4 1 1 1 2 1 2 1 14 1 1 3 1 6 3 8 0 0 1 0 2 4 12 4 6 4 2 0 6 2 0 5 8 0 14 8 0 4 1 4 5 2 2 2 0 6 0 1 1 1 10 8 2 2 6 8 8 3 3 0 0 2 1 10 2 6 2
result:
ok 146 tokens
Test #9:
score: 0
Accepted
time: 15ms
memory: 3712kb
input:
128 ?11?10?0 11?11110 ?11001?? ??1?0??1 01011011 ?100?01? ???0?11? ?1?1?000 ??11?000 ???000?1 011111?? 1??1?10? 00??0?1? ?1000010 0?0???0? 01101110 11010??0 11??10?1 ?0?000?0 100?0011 0???110? 1?010001 ?10?0??0 0?01?01? ?0??0000 0?0001?0 000101?1 0?1?001? 1?01??01 0???01?? 0100??0? ??01???0 10110010...
output:
0 1 0 4 1 1 2 0 0 1 1 4 2 0 10 0 1 1 5 0 1 0 4 2 4 2 0 1 1 5 3 6 0 0 0 0 3 1 1 0 0 1 3 0 0 1 4 0 0 1 1 1 0 0 0 1 0 0 3 0 2 2 2 0 1 9 0 0 0 1 8 0 1 0 0 3 0 1 14 9 4 0 0 5 1 0 1 5 6 0 1 1 1 3 3 0 2 0 3 0 2 0 2 3 0 5 2 4 8 1 1 2 1 2 0 0 0 7 0 1 2 0 1 2 1 0 0 2
result:
ok 128 tokens
Test #10:
score: 0
Accepted
time: 15ms
memory: 3840kb
input:
113 1110??1?0 ??0?101?1 10?001000 00???01?? 01?01??1? 00??11?0? 000?1011? ?0110?001 00111??0? ???0???00 ??0100?0? ?0000?000 ?00?01??? 0????1?01 ??000?11? 00???01?1 1?0?0111? ?11?0011? 11?0?00?0 ??111?11? ?1101010? 0?1101001 000?10011 ?011101?? 1?1?11??1 ?1001?1?1 001010?00 1?0?01010 0????1000 001??1...
output:
1 2 1 3 2 0 0 0 0 13 4 4 3 3 0 1 0 0 0 7 1 0 0 1 7 1 0 2 2 0 2 1 1 5 1 2 2 0 3 3 1 2 1 0 1 8 3 2 2 0 0 1 0 0 1 0 2 1 0 1 0 0 1 3 3 0 1 2 6 3 3 3 0 2 1 4 1 0 0 0 2 1 1 0 1 1 0 3 1 1 0 0 2 1 1 1 2 9 0 0 0 1 3 3 1 1 0 8 1 0 2 5 2
result:
ok 113 tokens
Test #11:
score: 0
Accepted
time: 15ms
memory: 3840kb
input:
102 1?10?0?011 ?1??11???? ?001?01?01 0??100?010 0000???101 11111100?1 1?01?011?0 0011011010 ?11?1?0?01 ?1?1110?10 011?001110 1?101011?0 ?0?1100?1? 111?0110?? 1??00??010 ??1?1?11?0 1??01001?? 11??00?0?0 0???00??00 00??1011?1 1011001?00 1001?0?1?1 ??0001101? ?10?110100 10?00?0011 ??100????1 ?0?01110?1...
output:
0 14 1 2 0 0 1 0 0 1 0 0 0 0 0 1 1 0 8 0 0 0 0 0 0 2 0 2 0 1 0 0 1 2 0 0 0 0 0 0 2 3 20 0 0 0 0 1 0 1 2 0 3 1 0 0 11 0 2 10 0 5 0 2 0 0 0 0 2 0 2 0 2 5 1 2 0 0 0 1 0 5 1 0 14 1 0 0 1 1 0 4 0 3 0 0 1 3 1 0 0 1
result:
ok 102 tokens
Test #12:
score: 0
Accepted
time: 12ms
memory: 3712kb
input:
103 ?????0???? ??????0??? ????????0? ???????0?? ?????????1 ??0??????? ????1????? ?1???????? ???1?????? ???????1?? ????0????? ????1????? ????????1? ???????1?? ??????1??? ????????1? ??1??????? ??0??????? 1????????? ?1???????? 1????????? ???0?????? ????0????? ???0?????? ??0??????? ?1???????? ???1??????...
output:
32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 ...
result:
ok 103 tokens
Test #13:
score: 0
Accepted
time: 15ms
memory: 3840kb
input:
103 0??0?????? 1??1?????? ?1???0???? ???0????1? ??0??1???? ????1?1??? ???0?????1 ????????1? ?????0???? ?????01??? ???0???1?? ????????1? ??0??1???? ?????????1 ??0????1?? ?0????1??? ???0?0???? ?0??1????? 0?????0??? ????1????0 1??????0?? ???1??1??? ?????1?0?? ?0???????0 ??????0??? ?0???????1 00????????...
output:
23 23 12 9 9 20 12 32 32 15 12 32 9 32 9 9 20 9 20 9 9 23 12 20 32 12 17 32 15 23 9 12 12 20 12 12 12 15 17 32 17 20 23 23 17 17 15 20 12 20 15 9 20 9 15 20 17 23 20 23 12 20 17 9 15 32 20 12 9 23 12 12 23 23 12 9 23 17 15 9 23 20 20 15 23 20 12 23 17 23 32 12 9 17 20 20 20 9 20 20 9 17 6
result:
ok 103 tokens
Test #14:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
21 ???????????????????????????????????????1?????????? 0????????????????????????????????????????????????? ??????????1??????????????????????????????????????? ???????????????????????????????????????????????1?? ?????????????????????????????????????????0???????? ??????????????????????????????????????????...
output:
782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 782 151
result:
ok 21 tokens
Test #15:
score: 0
Accepted
time: 15ms
memory: 3840kb
input:
21 ????????????????????????????0?????0??????????????? ?0????????????????????????????1??????????????????? ???0????????0????????????????????????????????????? ?????????????????????????????????????0?????0?????? ???????????????????????????????????0????????????0? ?????????????????0?????????????0??????????...
output:
518 239 543 518 525 518 239 518 257 257 482 257 518 264 525 482 525 239 525 543 104
result:
ok 21 tokens
Test #16:
score: 0
Accepted
time: 15ms
memory: 3712kb
input:
21 ???11????????????????????????0???????????????????? ?????1????????1???????????????0??????????????????? ???????1??????????????????????????1??????????????? ??1?0????????????????????????????????0???????????? ????????????????????????????????????00???????????0 ?????????????0????1???????1???????????????...
output:
66 141 525 132 327 125 123 123 264 150 123 375 368 123 402 132 150 132 386 132 63
result:
ok 21 tokens
Test #17:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
21 ?????????1???????????????10?????1????????????????? ????????????????????????0?01?????????????????????0 ?????????????????????0????0????????0???????0?????? ??????????????????????????????1???????????1???0?1? ????????????????01???????????0??????????0????????? ???????1?1?????????????????????????0??????...
output:
109 110 321 83 119 78 45 49 310 50 150 23 42 68 86 66 150 64 78 313 6
result:
ok 21 tokens
Test #18:
score: 0
Accepted
time: 15ms
memory: 3840kb
input:
11 ????????????????????????????????0??????????????????????????????????????????????????????????????? ????????????????????????????????????????????????????????????????????????????????????0?????????????? ???????????????????????????????????????????????????????0?????????????????????????????????????????? ?...
output:
2391 3386 3152 3386 3602 4657 3386 3245 3386 1922 1220
result:
ok 11 tokens
Test #19:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
11 ??1???????????????????????????????????????????????1??????????????????????????????????????????????? ??????????????????????????1????????????????????????????????????????????????????????1???????????????? ???????????????????????????????????????????????????0???????????????????????1??????????????????? ?...
output:
2096 1919 1158 1072 954 3089 1906 2141 1059 1112 629
result:
ok 11 tokens
Test #20:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
11 ??????0????????0????????????????????????????????????????????????????????1??????????????????????? ????????????????1???????????1?????????????1???????????????????????????????????????????????? ???????????????0???????1??????1??????????????????????????????????????????????????????????????? ?????????????...
output:
406 1658 552 404 312 560 558 552 552 783 238
result:
ok 11 tokens
Test #21:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
11 ?????0????????????????????????????????????0???????????????????????????????1???0???????????? ??????????????????????????????0????????????????0????????????????????????????????????????1???????0??? ?????????1??????????????0????????????????????????????????00?????????????????????????????????? ?????????1...
output:
337 291 225 216 172 1262 666 347 467 165 212
result:
ok 11 tokens
Test #22:
score: 0
Accepted
time: 16ms
memory: 3712kb
input:
4 ??????????????????????????????????1????????????????????????????????0?????0??????????????????????????????????????0????????????????????????????????????????????????????????????????????????????????????????????????????1????????????1???????????????????????0???????????????0??????????0????????????????????...
output:
2 75 15 3
result:
ok 4 tokens
Test #23:
score: 0
Accepted
time: 16ms
memory: 3712kb
input:
4 ??????1???1????????????????????????????????0?????????1?????????????????0??????????????????????????????????????????????????????????????????1?????1??????????????????1????????????0????????????????????????????????????????0???????????????????????????????????????????????????????0????????????????????????...
output:
0 0 0 0
result:
ok 4 tokens
Test #24:
score: 0
Accepted
time: 17ms
memory: 3840kb
input:
4 ????????????????????????0???????????0?????0???????0??0?0????1?0?1??????????????1???????????????????????????????0???????????????????????????1??????1???????0?????????????????????????????0?1??????????????0????????1???????00??????????1????0???1??0??1?????0???1???????????0????????????????????1? ???????...
output:
0 0 0 1
result:
ok 4 tokens
Test #25:
score: 0
Accepted
time: 16ms
memory: 3712kb
input:
4 ??????1???????????????????????1???1??????????????????0??10?????1?????????????????????????0?????1?????1??????????????????????1??????0????????????????????????????????01??1??????????????????1??1????????????????1????1??????????????0??????1???1?????????1??????????????????????1??1??1???????????1????????...
output:
0 0 0 0
result:
ok 4 tokens
Test #26:
score: -100
Wrong Answer
time: 13ms
memory: 3840kb
input:
1 ??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
1
result:
wrong answer 1st words differ - expected: '699052', found: '1'