QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#70685#5075. Fenwick Treenocriz#TL 2ms3412kbC++141.8kb2023-01-07 14:35:562023-01-07 14:35:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-07 14:35:59]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3412kb
  • [2023-01-07 14:35:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define int long long
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<ll> vl;


template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

const int MOD = 998244353;
int add(int x, int y) { return x+y>=MOD?x+y-MOD:x+y; }
int sub(int x, int y) { return x-y<0?x-y+MOD:x-y; }
int mul(int x, int y) { return 1LL*x*y%MOD; }
int qpow(int x, int y) {
    int ret = 1;
    for(;y; y >>= 1, x = mul(x,x))
        if(y & 1) ret = mul(ret, x);
    return ret;
}
int inv(int x) { return qpow(x,MOD-2); }

void solve() {
    int n, ans = 0; 
    cin >> n;
    string s;
    cin >> s;
    s = "0" + s;
    for(int i = 1; i <= n; i++) {
        int c = __builtin_ctz(i);
        int nonzero = 0, p = i-1;
        debug(i);
        for(int j = 0; j < c; j++) {
            debug(p);
            if(s[p] != '0') nonzero++;
            p -= (1<<j);
        }
        if(s[i] == '1') {
            if(nonzero == 0) {
                ans++;
            }
        } else {
            if(nonzero == 1) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3412kb

input:

3
5
10110
5
00000
5
11111

output:

3
0
3

result:

ok 3 number(s): "3 0 3"

Test #2:

score: -100
Time Limit Exceeded

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
2
2
0
0
0
2
0
1
2
0
0
1
2
2
0
2
1
0
0
2
2
2
0
2
2
2
0
2
2
0
0
2
2
0
0
2
0
2
2
0
0
0
0
0
0
0
2
2
2
2
0
1
0
2
2
0
2
2
0
2
2
0
1
0
2
0
0
2
2
0
0
0
1
2
0
2
0
0
0
0
2
2
0
0
0
0
0
0
2
0
2
2
0
2
2
2
0
0
0
0
0
0
0
1
0
0
0
2
0
2
0
0
0
2
0
2
0
0
2
0
0
0
1
0
0
1
2
0
0
2
0
2
0
0
2
0
2
0
0
0
2
0
0
2
2
1
0
...

result: