QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310136#8129. Binary Sequenceucup-team992#WA 125ms4176kbC++201.5kb2024-01-21 03:41:502024-01-21 03:41:51

Judging History

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

  • [2024-01-21 03:41:51]
  • 评测
  • 测评结果:WA
  • 用时:125ms
  • 内存:4176kb
  • [2024-01-21 03:41:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define F first
#define S second
typedef int uci;
#define int long long

vector<bool> bin(int x) {
    vector<bool> res;

    bool start = false;
    for (int k = 30; k >= 0; k--) {
        if (x>>k&1) {
            start = true;
        }
        
        if (start) {
            res.push_back(x>>k&1);
        }
    }

    return res;
}

vector<bool> next_seq(vector<bool>&a) {
    vector<bool> res;

    int j = 0;
    for (int i = 0; i < size(a);) {
        while (j < size(a) && a[j] == a[i]) {
            j++;
        }

        vector<bool> part = bin(j-i);
        res.insert(res.end(), part.begin(), part.end());
        res.push_back(a[i]);

        i = j;
    }

    return res;
}

const int MAXM = 1e6;

void solve(){
    vector<vector<bool>> seqs = {{1}, {1, 1}};

    while (size(end(seqs)[-2]) < MAXM) {
        seqs.push_back(next_seq(seqs.back()));
    }

    // int bad = 0;
    // for (int i = 2; i < size(seqs); i++) {
    //     for (int j = 0; j < size(seqs[i-2]); j++) {
    //         if (end(seqs[i-2])[-j-1] != end(seqs[i])[-j-1]) {
    //             bad++;
    //             cout << i << ' ' << j << '\n';
    //         }
    //     }
    // }
    // cout << bad << '\n';

    bool parity_last = size(seqs) % 2;

    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        m++;

        cout << end(seqs[size(seqs)-1 - (parity_last != (n&1))])[-m] << '\n';
    }
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
}

详细

Test #1:

score: 100
Accepted
time: 103ms
memory: 4176kb

input:

10
4 0
4 1
4 2
4 3
4 4
4 5
4 6
6 3
6 7
118999881999119725 3

output:

1
1
0
1
1
1
0
1
1
0

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 125ms
memory: 4088kb

input:

10
28 69772
10 7908
4 3198
4 85913
14 52729
3 20445
9 88912
17 23743
25 37356
2 97697

output:

1
1
1
1
1
1
1
1
1
1

result:

wrong answer 1st numbers differ - expected: '0', found: '1'