QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #303447 | #5075. Fenwick Tree | myusername# | WA | 16ms | 3920kb | C++20 | 568b | 2024-01-12 15:43:59 | 2024-01-12 15:44:00 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e16 + 7;
int LSB(int i){
return i & (-i);
}
int T,n;
char s[100010];
int cnt[100010];
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
for(int i = 0; i <= n; i++) cnt[i] = 0;
scanf("%s",s + 1);
int ans = 0;
for(int i = 1; i <= n; i++){
if(s[i] == '1' && cnt[i] == 0){
ans++;
cnt[i + LSB(i)]++;
}
if(s[i] == '0' && cnt[i] == 1){
ans++;
cnt[i + LSB(i)]++;
}
}
printf("%lld\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
3 5 10110 5 00000 5 11111
output:
3 0 3
result:
ok 3 number(s): "3 0 3"
Test #2:
score: -100
Wrong Answer
time: 16ms
memory: 3920kb
input:
100000 10 0000000000 10 0000000100 10 0000000000 10 1000000000 10 0000010000 10 0000000000 10 0000000000 10 0000000000 10 0100000000 10 0000000000 10 0000000001 10 0000001000 10 0000000000 10 0000000000 10 0000000001 10 0000100000 10 0010000000 10 0000000000 10 0010000000 10 0000000001 10 0000000000...
output:
0 1 0 4 2 0 0 0 3 0 1 2 0 0 1 3 3 0 3 1 0 0 2 2 3 0 2 3 3 0 3 2 0 0 4 2 0 0 2 0 3 3 0 0 0 0 0 0 0 2 3 3 2 0 1 0 2 2 0 2 3 0 2 4 0 1 0 2 0 0 3 3 0 0 0 1 3 0 2 0 0 0 0 2 2 0 0 0 0 0 0 2 0 2 2 0 3 4 2 0 0 0 0 0 0 0 1 0 0 0 4 0 2 0 0 0 2 0 3 0 0 2 0 0 0 1 0 0 1 2 0 0 2 0 3 0 0 2 0 3 0 0 0 3 0 0 3 3 1 0 ...
result:
wrong answer 4th numbers differ - expected: '2', found: '4'