Submission #202076

#	Time	Username	Problem	Language	Result	Execution time	Memory
202076		darkkcyan	CATS (NOI14_cats)	C++14	25 / 25	565 ms	8024 KiB

cats

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

void simulate(long long x, long long l, long long n) {
    vector<long long> s1, s2;
    bool s1_inv = 0;

    while (x) {
        if (!s1.size()) s1.push_back(0);
        if (!s2.size()) s2.push_back(0);
        s2.push_back(s1.back() ^ s1_inv);
        s1.pop_back();
        s1_inv ^= 1;
        if (s2.back() > l) {
            cout << (s2.back() & 1);
            --x;
        } else {
            s2.back() += 2ll * n;
            s1.push_back(s2.back() ^ s1_inv);
            s1.push_back(s2.back() ^ s1_inv);
            s2.pop_back();
            if (s2.size()) s2.pop_back();
        }
    }
}

const long long l2_inf = 62;
int main() {
    int ntest; cin >> ntest;  
    while (ntest--) {  
        long long x, l, n; cin >> x >> l >> n;  
        long long mul = l / n;  
        mul += 1 + (~mul & 1);  

        long long l2_period = min(l2_inf, mul / 2 + 1);
        --x;  
        x %= 1ll << l2_period;  

        cout << mul * n + (__builtin_popcountll(x) & 1) << '\n';  
    }  
    // cout << endl;  
    // simulate(1000, 9, 2);   
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5