QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#737448 | #7987. 替换 | MiniLong | AC ✓ | 2268ms | 4600kb | C++14 | 3.1kb | 2024-11-12 15:52:11 | 2024-11-12 15:52:13 |
Judging History
answer
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
#ifdef ONLINE_JUDGE
char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
#define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
#else
#define get() getchar()
#endif
template<typename T> inline void read(T &t){
T x = 0, f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
t = x * f;
}
template<typename T, typename ... Args> inline void read(T &t, Args&... args){
read(t);
read(args...);
}
template<typename T> void write(T t){
if(t < 0) putchar('-'), t = -t;
if(t >= 10) write(t / 10);
putchar(t % 10 + '0');
}
template<typename T, typename ... Args> void write(T t, Args... args){
write(t), putchar(' '), write(args...);
}
template<typename T> void writeln(T t){
write(t);
puts("");
}
template<typename T> void writes(T t){
write(t), putchar(' ');
}
#undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
const ll mod = 998244353;
ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
void add(ll &x, ll y){x = (x + y) % mod;}
void mul(ll &x, ll y){x = x * y % mod;}
ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 1e5 + 5;
int B = 500;
int n, ans[N];
char s[N], ch[N];
bitset<N> a, st, u;
int main(){
read(n), scanf("%s", s);
int tot = 0, num = 0;
_rep(i, 0, n - 1){
if(s[i] == '1') a[i] = 1;
if(s[i] == '?') st[i] = 1, num++;
tot += s[i] == '1';
}
if(!num){
_rep(i, 1, n) writeln(tot);
return 0;
}
_rep(i, 1, n){
if(i > B){
u = a;
for(int j = i; j < n; j += i){
u = u | ((u << i) & st);
}
ans[i] = u.count();
}else{
_rep(j, 1, n){
if(j <= i) ch[j] = s[j - 1] == '1' ? '1' : '0';
else ch[j] = s[j - 1] == '?' ? ch[j - i] : s[j - 1];
ans[i] += ch[j] == '1';
}
}
}
_rep(i, 1, n) writeln(ans[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
input:
5 10?1?
output:
3 4 2 3 2
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 2102ms
memory: 4600kb
input:
99974 ??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 99974 lines
Test #3:
score: 0
Accepted
time: 2237ms
memory: 4260kb
input:
99799 ??1?1??1??1?1?11?????1??01?1?????11?1??1?1?11?1?????????????1?011??????11??11??11??1?1?1??1?1??111?1?11????1?1???1??11??1?1??????1???1??11??1?1?111??111????1??1?10?11111?1?111??11????1?11??1?1??1???1?111???????1?11???1?1???11?011?111?1?111?11??11?11??11?111111???111?1?????1?11??????1??111??1??...
output:
89888 89936 89901 89871 89845 89936 89821 89823 89796 89650 89740 89764 89770 89749 89925 89871 89725 89869 89923 89778 89964 89782 89717 89716 89761 89848 89658 89756 89736 89900 89575 89764 89816 89855 89833 89951 89725 89857 89880 89755 89762 89896 89563 90020 89798 89805 89734 89838 90040 89822 ...
result:
ok 99799 lines
Test #4:
score: 0
Accepted
time: 2222ms
memory: 4316kb
input:
99385 1?1?11?0???11??1?1?1111?11?111?1???11???1???1?????01?1??1111?1???1?010?11?01?111111??????01011????1111111??11?1????11??11??1??11????1?01????1?11??0?11?1????0?1?0??11????110?10111?1111101?10??0?111??11????1?????0?11??11111??1?11111??0111?111???10111????1???11???1???1??11??????1??11?111???111111...
output:
89288 89419 89256 89391 89471 89211 89266 89343 89405 89434 89351 89315 89336 89419 89288 89323 89492 89385 89319 89245 89433 89296 89461 89313 89425 89291 89314 89510 89320 89326 89336 89397 89280 89260 89217 89289 89321 89365 89451 89297 89485 89239 89256 89382 89435 89420 89132 89305 89251 89395 ...
result:
ok 99385 lines
Test #5:
score: 0
Accepted
time: 2232ms
memory: 4252kb
input:
99444 1111??11101?111?1111?11?1111111????111111111?1?011111111???01111?00??01?11????11??1?111???1?1?1?????1011111?1??????1???11?1??1?1?110011????1??111?1??111110?11111?11111??1111??100111????1??11?111111101?1?1?1??1????1?1???1?1?11?1111?10?111????1??1011??11111?1?1??11?11?11?11??11?11???1???111??11?...
output:
89429 89531 89218 89350 89384 89203 89454 89476 89350 89414 89445 89330 89480 89347 89461 89449 89368 89258 89402 89348 89438 89392 89494 89460 89313 89436 89500 89353 89286 89503 89435 89350 89314 89492 89228 89367 89421 89227 89434 89503 89329 89256 89402 89308 89259 89448 89345 89415 89479 89299 ...
result:
ok 99444 lines
Test #6:
score: 0
Accepted
time: 2221ms
memory: 4384kb
input:
99113 1???1?11?11????1?11?111????011??1?1??10?1111110?1?1111?????????11???111?11?11??1?0??111???1?????1??11111????0??11?????????11?1?1111???1??1111111?110??1110??11?1??01??1??1??1??11?1??11?11?1?10?1?11????0111??1??1?11?11?0011111??11?1011???111111??111111?1111??11????1?111?11??????10?01?1??1111?1?1...
output:
89102 89103 89073 89074 89143 89127 89145 88982 89181 89102 88943 89072 89162 89188 89113 89179 89020 89154 89201 89251 89020 89182 89204 89253 89242 89118 89040 89253 89082 89214 89193 89152 89127 89109 89237 89082 89199 89094 89012 89108 89039 89006 88971 89096 89088 89098 89234 89189 89024 89192 ...
result:
ok 99113 lines
Test #7:
score: 0
Accepted
time: 2227ms
memory: 4316kb
input:
99461 ??1111?0011101?111??110??1?10?1111??11?1?10111?110?01?1?1?1?10??0?1?1?111?1?111?111100?1??11111?1?1?11???111111?111111?11??1???11?11??11?111??111111??11011?1?100?110?111?1111110?1011?11?10?111?????1110?110???0?1???111???111??11??11???1?11111???1?1111???11??11?1?11111??11???011?1?????11111?1?0?...
output:
89485 89289 89473 89325 89438 89154 89382 89204 89441 89356 89441 89254 89464 89335 89388 89245 89356 89288 89328 89397 89338 89413 89317 89270 89327 89331 89449 89328 89436 89330 89296 89301 89202 89278 89283 89359 89241 89266 89468 89230 89280 89352 89308 89369 89325 89215 89403 89297 89370 89405 ...
result:
ok 99461 lines
Test #8:
score: 0
Accepted
time: 2216ms
memory: 4312kb
input:
99496 11111?11?111?110111?1?110?111?111?0111?101?111111?111?1??11?1?11?11011111?111?111??1?111?11111?1011?111?1??1?1111111?01???10???1?111?1???11?1111110???01111?11?1?101111?1?11101?11001?1???1?1111???1?1111?1?110??1101?11??101?1111??10?11???1???1111?11????1?0?011?11111111111?1??111?11?101?01?110?11...
output:
89376 89296 89387 89289 89277 89463 89358 89328 89297 89429 89385 89476 89544 89340 89496 89368 89296 89285 89277 89345 89228 89388 89404 89276 89372 89474 89345 89291 89381 89337 89417 89444 89309 89341 89306 89306 89383 89411 89405 89343 89289 89339 89255 89376 89390 89549 89381 89319 89313 89297 ...
result:
ok 99496 lines
Test #9:
score: 0
Accepted
time: 2167ms
memory: 4288kb
input:
99529 1110??11111??1101?11?1?1011111101?0?11?1?1?111?0?101?01111?1?1?1011??1110?1?11111110?11?11111?110?111??11?11011?1?1101??1??1111???1?1110111?11?11011111?1111?0??111111110111?11?111?1?111?111?1111111?10110?11??111???1111??11?11111?1?10?110111?1111111?111?11?111111111??1011?1111111???11?11111?111...
output:
89820 89867 89716 89630 89663 89911 89895 89743 89663 89700 89791 89639 89753 89741 89780 89778 89838 89714 89795 89804 89806 89776 89741 89754 89623 89791 89673 89824 89717 89713 89699 89656 89768 89760 89838 89822 89757 89794 89740 89719 89728 89833 89707 89727 89722 89669 89665 89633 89842 89719 ...
result:
ok 99529 lines
Test #10:
score: 0
Accepted
time: 2192ms
memory: 4316kb
input:
99400 1?11??11111010111111011111?111111?1111?11111111111111?1111111111???1??1?111?1111?11111???11?101??1?1?111?11?1110?11?111?11?0?1??1?111111010111111?1?11?111?111111011100111?01111?11111111?10??11?111?10101??11111?1111?1?11111111?1?11?1111?0?1??0101?11?111?11111101?0?011??110?1111111111??1??11?111...
output:
89462 89486 89613 89523 89540 89487 89623 89541 89558 89591 89571 89600 89489 89590 89700 89544 89555 89543 89692 89489 89564 89600 89665 89564 89577 89475 89494 89629 89440 89510 89624 89536 89524 89583 89488 89609 89483 89537 89449 89561 89522 89471 89543 89670 89476 89588 89635 89484 89602 89553 ...
result:
ok 99400 lines
Test #11:
score: 0
Accepted
time: 2111ms
memory: 4312kb
input:
99600 11111010?0?1?111101??11110011111?0??1?0?111?1111111111111010?11111?1111111?11?1111111111?1?1?11111111111?1?1110111111111111?11?1111?11111?11111111?0011?1??01???111??011111?1111111?011111111?10111110?11110?11?1??101?101??111?111110111111?11??111?1111111111?11111111??1?101111?011111?1?110?11101?...
output:
89763 89704 89659 89735 89760 89745 89694 89654 89693 89703 89668 89792 89637 89721 89690 89698 89697 89623 89699 89672 89727 89711 89717 89636 89687 89706 89619 89703 89605 89660 89756 89768 89653 89695 89666 89583 89677 89723 89658 89629 89628 89628 89598 89791 89682 89655 89627 89723 89661 89725 ...
result:
ok 99600 lines
Test #12:
score: 0
Accepted
time: 2088ms
memory: 4376kb
input:
99857 ??11111111?11111111111?111011?111?111010111111101111110?10111?11?11111111111111111111111?1111?1111110110?1111?1110111???1?11111?101111011?111111111111111?10111110101?11011111?11110111?1101111?111111111111111111111?111111111111111111111111?1111?1?1110?1101?11011111?111111011111111111?1001111110...
output:
89878 89807 89810 89855 89742 89805 89827 89760 89829 89880 89695 89840 89812 89882 89844 89812 89854 89837 89817 89807 89695 89849 89822 89811 89739 89826 89807 89842 89821 89820 89815 89819 89765 89864 89839 89835 89828 89824 89759 89870 89850 89824 89829 89833 89836 89859 89820 89802 89898 89777 ...
result:
ok 99857 lines
Test #13:
score: 0
Accepted
time: 2129ms
memory: 4320kb
input:
99187 ?????????????????1????????????????????1???????????1???????1???????????????????????????????????????????1????????????????????????1???1??????????????????????????????????????????????????1??????????????????????????0???????????1?????????????????????????????????????????????1??????????????????????????...
output:
88324 88528 89220 88945 88564 88984 88452 89296 89280 88711 88510 89219 88838 87914 88413 88674 88487 88687 88305 88651 88433 87860 88689 88718 88354 88787 88408 88406 88491 88736 88444 88580 88419 87701 87569 88012 88926 88139 88212 87998 87411 87356 87504 87816 88447 88194 87201 87743 87737 87422 ...
result:
ok 99187 lines
Test #14:
score: 0
Accepted
time: 2057ms
memory: 4388kb
input:
99387 11111?111101?1111?1111111?1?1011111?10111?1111111110111111?0?11110111111111111111111111?11110???1?111011?111111111111111111111101111111111111??111110111111110001111101?111?11?110011110001111011111111111?10?1111011?1101101111101111111010111111111111??1111111110111111111?0111110?01?111?1111?1101...
output:
89563 89475 89488 89489 89478 89532 89520 89550 89494 89503 89439 89484 89474 89480 89499 89513 89493 89469 89529 89529 89470 89484 89459 89464 89489 89514 89464 89481 89508 89462 89474 89466 89477 89469 89522 89496 89456 89535 89475 89425 89524 89466 89503 89503 89469 89483 89456 89458 89508 89498 ...
result:
ok 99387 lines
Test #15:
score: 0
Accepted
time: 2067ms
memory: 4252kb
input:
99952 11111011110111111?11111111111110111111111011111111111?11111111?11111111111?1110101111111111?1111111?11111111110111111111110?1111?1?111111111111101111111111?1111111011111111101111111111111111111111111111111111110111111111111111111011001111111?11111111110101111111001111111?111111001111?111011110...
output:
89992 90008 90025 89973 90022 89993 89978 90019 89991 89987 89990 89990 90009 89992 90030 90027 90006 89971 90025 90028 90000 90013 89950 89992 89995 90028 90015 89995 89993 90036 90029 90009 90003 89985 90017 90008 89987 89981 89966 89986 90016 90023 90014 90049 89955 89965 89976 89986 90025 89984 ...
result:
ok 99952 lines
Test #16:
score: 0
Accepted
time: 4ms
memory: 3888kb
input:
99361 011111011111011111111101111111111111111111111111111111111111111111111101111111101111111111111111101111111111111111111111111111101111111111111111011111101111111111011110111110111101101011111111011111111111111111111111111111111101111111111111011111111101111101111111111011111111111111111111111111...
output:
89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 89334 ...
result:
ok 99361 lines
Test #17:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 2095ms
memory: 4332kb
input:
99734 1??1?????1????????0????????1???????????1??????????????????????1??1?????????1??????????1?1????????????0?????0?1???1???1??????????????????1???????1????1????0???1?????????????1??1????????????1????????????????????????????????????????????1??????????????????1????????????????1??????1?1??????????1????...
output:
90250 89684 90348 89901 90397 90228 89768 89793 89760 90316 89612 89596 90260 89494 89939 89827 89358 90044 90203 89932 89632 89741 90050 89963 90413 90052 90126 89426 89351 89548 89701 89792 89611 89695 89505 89200 89452 90103 89420 89759 89749 89527 89670 89943 89585 89679 90359 90361 89500 90120 ...
result:
ok 99734 lines
Test #19:
score: 0
Accepted
time: 2111ms
memory: 4264kb
input:
99856 ???????1??1?????????????10??0?????1?????1????????1??1???1?????1????????1????1?1??0??????1?????1???11???1??1????1????????????11?1?1????1???????????????11???1???1????????1???11?11??1?1???????1?????????????11????????????????1?1??????????1???1???1???????????????1???????1??????????11?????????1??1??...
output:
90373 90324 89898 90355 89852 90399 90467 90189 89908 90401 90286 90148 90425 90284 90312 89951 90077 90346 90236 90019 90313 90354 90546 90089 89994 90424 90316 90091 90621 90428 90471 90406 90170 90108 90832 90369 90120 90201 90205 90241 90213 90016 90354 89912 89839 90015 89907 89829 89976 89799 ...
result:
ok 99856 lines
Test #20:
score: 0
Accepted
time: 2084ms
memory: 4588kb
input:
99103 1???1????1??1????????????????1??????1?1????????11?????????????1??11????????1??1???????????????????1?1????11?????????????1????1??????1???????????1?????11??1?11?????0???????1????1??????1??1??????11?????????1?????????1??????????????11?????????1?????1????????1?????????????1?1????1???????1????1???1...
output:
88940 89121 89020 89110 89197 88922 88969 88964 89094 88867 88899 89313 88935 88928 88992 88814 89162 89020 88740 88949 88587 89028 88884 89211 88375 88949 89453 88685 88580 88448 88709 88472 88678 88723 88474 89150 89035 88857 88489 88693 88912 88871 88781 88728 89033 88585 88862 88914 88614 88427 ...
result:
ok 99103 lines
Test #21:
score: 0
Accepted
time: 2268ms
memory: 4576kb
input:
99126 ?1???????1????????1????????11????11??1?11????1?0??1???????11?11???????????????1??????11??0??????????????1?1????????1????1???1???1?1??11???1?????1????????????????????1?1?????????1???01??1?1??1?11?0????1??????1???00????1????????????1??1????1??????????1????1?????11?1????1????????0?????1?011?1?1??...
output:
88472 88604 88721 88612 88760 88694 88963 88666 89086 88703 88811 88751 88636 88967 88666 89104 88584 89058 88673 88545 88895 88820 88756 88794 88494 88613 88741 88783 89116 88387 88933 88793 88694 88630 88530 88819 88710 88886 88848 88795 88597 88936 88851 88610 89017 88529 88820 89022 88464 88711 ...
result:
ok 99126 lines
Test #22:
score: 0
Accepted
time: 2146ms
memory: 4320kb
input:
99153 ?????????1?????1???????1111????1?1?11???11???????0???1??11???10?????1??????11?????1???1?1????1??????111?1???11??????????111????????????????1??1????11??111????11???1????1???11??????????11????1?????111??????1???111???11???0???0???1????1111?1???1?????1??1????????1???1???1?11??1?01??1??????????1??...
output:
89246 89332 89245 89102 89231 89096 89406 89109 89166 89386 89117 88958 89277 88928 89447 89180 88910 89044 89249 89123 89263 89099 89293 88992 89033 89177 89390 89311 89037 89132 89029 89351 89332 88947 88997 89146 89120 89264 89158 89202 89280 89160 89054 88894 89085 89203 89359 88864 89129 89133 ...
result:
ok 99153 lines
Test #23:
score: 0
Accepted
time: 2178ms
memory: 4332kb
input:
99867 11?1????1?1??11??1?11???11???1?1??1?1?001?1?11??11?1?1???????11???1????11111???1?11?????1???????1??10?1???1?????100???11??1???????????11?????1??1???1???1??11????1??11???????1???11??????????10??1?????????11????1???1???1?????111111?1?????1111?11?????11??11111?1???110??11?11????1???1???????11?1?1...
output:
89900 89954 89984 90026 90281 90038 89853 90009 90097 89862 90104 90038 89842 89732 90136 89916 89709 89958 90062 90040 89843 90274 89980 90034 89947 89940 90111 89742 89693 89837 89893 89859 90114 89804 89936 90004 89993 89819 90045 89852 89893 89901 89794 89872 89836 90054 89641 89695 89960 89923 ...
result:
ok 99867 lines
Test #24:
score: 0
Accepted
time: 2247ms
memory: 4332kb
input:
99574 ?1?1??????111??1?1?1??11?1?1???0??1?0?11?1?1?1?1?1???1??11????1?1?1???11??????11?1????1?11?????1?????1??1?111?1??11???1?????????1??1????1?11???????1?11?????????11111?????1???1??11???10???0?1??????1110?111?1????????????00?1????????1??1????1?1?1??11?????0???1???110111110?1?11?11???1??1?1???0??11...
output:
89767 90101 90131 90028 89884 90232 89997 89844 89826 90017 89768 89967 89960 90056 89747 89695 89750 89811 89522 89967 89742 89702 89876 89846 90131 89798 89548 89863 89639 89642 90001 89616 89767 89716 89707 89739 89840 89532 89692 89859 89964 89702 89786 89718 89731 89780 89772 89897 89949 89787 ...
result:
ok 99574 lines