oj.uz

Submission #519348

# Submission time Handle Problem Language Result Execution time Memory
519348 2022-01-26T08:44:36 Z KoD Sob (COCI19_sob) C++17
0 / 110
 1000 ms 332 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<pair<int, int>> ans;
    vector<int> X(N), Y(N);
    std::iota(X.begin(), X.end(), 0);
    std::iota(Y.begin(), Y.end(), M);
    while (N > 0) {
        int L = 1;
        while (L < N) {
            L <<= 1;
        }
        const int m = M & (L - 1);
        const int H = L / 2;
        if (m < H) {
            const int len = N - m;
            for (int i = 0; i < len; ++i) {
                ans.emplace_back(X[i + m], Y[i]);
            }
            N -= len;
            M = m + len;
            X.erase(X.end() - len, X.end());
            Y.erase(Y.begin(), Y.begin() + len);
        } else {
            if ((m + N) - L >= H) {
                const int offset = L - m;
                for (int i = 0; i < H; ++i) {
                    ans.emplace_back(X[i], Y[i + offset]);
                }
                N -= H;
                M = m - H;
                X.erase(X.begin(), X.begin() + H);
                Y.erase(Y.begin() + offset, Y.begin() + offset + H);
            } else {
                for (int i = N - H; i < N; ++i) {
                    if (m + i >= L) {
                        ans.emplace_back(X[m + i - L], Y[i]);
                    } else {
                        ans.emplace_back(X[m + i - H], Y[i]);
                    }
                }
                X.erase(X.begin(), X.begin() + H);
                Y.erase(Y.end() - H, Y.end());
                N -= H;
                M = m - H;
            }
        }
    }
    for (const auto& [x, y] : ans) {
        assert((x & y) == x);
        std::cout << x << ' ' << y << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Execution timed out 1089 ms 204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Execution timed out 1083 ms 204 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Execution timed out 1089 ms 204 KB Time limit exceeded
4 Halted 0 ms 0 KB -