oj.uz

Submission #202076

# Submission time Handle Problem Language Result Execution time Memory
202076 2020-02-13T14:07:53 Z darkkcyan CATS (NOI14_cats) C++14
25 / 25
 565 ms 8024 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 248 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 760 KB Output is correct
2 Correct 45 ms 760 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 6392 KB Output is correct
2 Correct 565 ms 8024 KB Output is correct