제출 #519349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519349		KoD	Sob (COCI19_sob)	C++17	110 / 110	78 ms	15156 KiB

sob

#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: 10 / 10
• Subtask 2: 29 / 29
• Subtask 3: 39 / 39
• Subtask 4: 32 / 32