QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #89651 | #5075. Fenwick Tree | poi | WA | 18ms | 3748kb | C++14 | 634b | 2023-03-20 20:40:29 | 2023-03-20 20:40:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep( i , a , b ) for( int i = (a) , i##end = (b) ; i <= i##end ; ++ i )
const int MAXN = 2e5 + 10;
int n;
char ch[MAXN];
int main() {
int T;
cin >> T;
while( T-- ) {
scanf("%d",&n);
scanf("%s",ch + 1);
int res = 0;
rep( i , 1 , n ) {
int t = ( i & -i ) >> 1 , cn0 = 0 , cn1 = 0;
while( t > 0 ) {
if( ch[i ^ ( i & -i ) ^ t] == '1' ) ++ cn1;
else ++ cn0;
t >>= 1;
}
if( ch[i] == '1' ) {
if( !cn1 ) ++ res;
} else {
if( cn1 == 1 ) ++ res;
}
// cout << res << endl;
}
printf("%d\n",res);
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3748kb
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: 18ms
memory: 3528kb
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 1 0 0 0 3 0 1 1 0 0 1 2 1 0 1 1 0 0 2 2 1 0 2 2 3 0 2 1 0 0 4 2 0 0 1 0 3 3 0 0 0 0 0 0 0 1 2 1 2 0 1 0 2 2 0 1 3 0 2 4 0 1 0 1 0 0 1 3 0 0 0 1 3 0 1 0 0 0 0 2 2 0 0 0 0 0 0 1 0 1 1 0 2 4 2 0 0 0 0 0 0 0 1 0 0 0 4 0 1 0 0 0 2 0 3 0 0 1 0 0 0 1 0 0 1 1 0 0 2 0 3 0 0 2 0 2 0 0 0 3 0 0 3 1 1 0 ...
result:
wrong answer 4th numbers differ - expected: '2', found: '4'