oj.uz

Submission #155962

# Submission time Handle Problem Language Result Execution time Memory
155962 2019-10-02T09:49:07 Z Minnakhmetov CATS (NOI14_cats) C++14
25 / 25
 95 ms 8056 KB 
// #include <bits/stdc++.h>
   
// #define ll long long
// #define all(aaa) aaa.begin(), aaa.end()
 
// using namespace std;

// int f(ll x, ll y) {
//     if (x == 0)
//         return 0;
//     if (x < y / 2)
//         return f(x, y / 2);
//     return f(x - y / 2, y / 2) ^ 1;
// }
 
// signed main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
 
//     int q;
//     cin >> q;
 
//     while (q--) {
//         ll x, l, n;
//         cin >> x >> l >> n;
//         x--;
//         cout << x << "\n";

//         ll ans = 2 * (l / (n << 1) + 1) * n;

//         cout << (ans ^ f(x, 1ll << 61)) << "\n";
//     }
 
//     return 0;
// }

#include <bits/stdc++.h>
   
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;
 
struct MyStack {
    vector<int> v;
    int flip = 0;
 
    void push(int x)  {
        v.push_back(x);
    }
 
    int pop() {
        if (!v.empty()) {
            int x = v.back();
            v.pop_back();
            return x;
        }
        return flip;
    }
 
    int top() {
        return v.empty() ? flip : v.back();
    }
 
    void add() {
        push(pop() + pop());
    }
};
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int q;
    cin >> q;
 
    while (q--) {
        ll x, l, n;
        cin >> x >> l >> n;

        ll h = l / (n << 1) + 1;
 
        ll ans = 2 * h * n;

        x--;

        if (h <= 62)
            x %= (1ll << (h + 1));

        while (x > 0) {
            ans ^= (x & 1);
            x >>= 1;
        }

        cout << ans << "\n";
    }
 
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2296 KB Output is correct
2 Correct 95 ms 8056 KB Output is correct