結果

問題 No.1306 Exactly 2 Digits
ユーザー t33ft33f
提出日時 2020-12-06 13:43:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 4,941 bytes
コンパイル時間 1,703 ms
コンパイル使用メモリ 119,840 KB
最終ジャッジ日時 2025-01-16 18:24:56
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <numeric>
#include <random>
#include <map>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

bool interactive = true;

pair<int, int> diff(int x, int y, int n) {
    int p = x / n - y / n, q = x % n - y % n;
    if (p > q) swap(p, q);
    return {p, q};
}

int n = -1;
int qcount = 0;
vector<int> ans;

template<typename T>
void random_shuffle(vector<T> &a) {
    mt19937 mt{ random_device{}() };
    for (int i = a.size() - 1; i >= 1; i--) {
        uniform_int_distribution<int> dist(0, i);
        int j = dist(mt);
        if (i != j) swap(a[i], a[j]);
    }
}

void initialize_ans(int size) {
    n = size;
    ans.resize(n * n - n);
    iota(ans.begin(), ans.end(), n);
    random_shuffle(ans);
    // ans = {3, 5, 6, 8, 4, 7};
    cerr << "initialize with size = " << size << endl;
    cerr << "ans =";
    for (int x : ans) cerr << ' ' << x;
    cerr << endl;
}

int getsize() {
    int tmp; cin >> tmp;
    if (cin.eof()) {
        interactive = false;
        initialize_ans(10);
        return n;
    }
    return n = tmp;
}

pair<int, int> query(int i, int j) {
    if (!interactive) {
        ++qcount;
        assert(qcount <= (n * n - n) / 2 * 3);
        auto [p, q] = diff(ans[i], ans[j], n);
        cerr << "? " << i << ' ' << j << endl;
        cerr << p << ' ' << q << endl;
        return {p, q};
    } else {
        cout << "? " << i+1 << ' ' << j+1 << endl;
        int x, y; cin >> x >> y;
        return {x, y};
    }
}

void answer(vector<int>& r) {
    if (!interactive) {
        cerr << '!';
        for (int x : r) cerr << ' ' << x;
        cerr << endl;
        assert(r.size() == n * n - n);
        for (int i = 0; i < r.size(); i++) {
            assert(r[i] == ans[i]);
        }
    } else {
        cout << '!';
        for (int x : r) cout << ' ' << x;
        cout << endl;
    }
}

int main() {
    int n = getsize();
    vector<pair<int, int> > res(n*n-n);
    vector<int> ans(n*n-n, 0);
    for (int i = 1; i < n * n - n; i++) {
        res[i] = query(0, i);
    }
    auto sum = [](pair<int, int> x) { return x.first + x.second; };
    auto cmp = [sum](pair<int, int> x, pair<int, int> y) { return sum(x) < sum(y); };
    int idx10 = max_element(res.begin(), res.end(), cmp) - res.begin();
    if (sum(res[idx10]) < 0) idx10 = 0;
    int idxnn = min_element(res.begin(), res.end(), cmp) - res.begin();
    if (sum(res[idxnn]) > 0) idxnn = 0;
    // cerr << idx10 << ' ' << idxnn << endl;
    if (idx10 == 0) ans[0] = n;
    else if (idxnn == 0) ans[0] = n * n - 1;
    else {
        for (int x = n; x < n * n; x++)
            if (diff(x, n, n) == res[idx10] &&
                diff(x, n * n - 1, n) == res [idxnn]) {
                assert(ans[0] == 0);
                ans[0] = x;
            }
    }
    // cerr  << "a[0] = " << ans[0] << endl;

    map<pair<int, int>, vector<int> > idx_of;
    for (int i = 1; i < n * n - n; i++)
        idx_of[res[i]].push_back(i);
    for (auto &[k, v] : idx_of) {
        auto [p, q] = k;
        // cerr << p << ' ' << q << " =>";
        // for (int x : v) cerr << ' ' << x;
        // cerr << endl;
    }
    for (auto &[k, v] : idx_of) {
        auto [p, q] = k;
        int a0 = ans[0] / n - p, a1 = ans[0] % n - q,
            b0 = ans[0] / n - q, b1 = ans[0] % n - p;
        auto ok = [n](int x) { return 0 <= x && x < n; };
        int a = ok(a0) && ok(a1) ? (ans[0] / n - p) * n + (ans[0] % n - q) : -1,
            b = ok(b0) && ok(b1) ? (ans[0] / n - q) * n + (ans[0] % n - p) : -1;
        if (v.size() == 1) {
            const int i = v[0];
            // cerr << p << ' ' << q << ' ' << i << ' ' << a << ' ' << b << endl;
            if (n <= a && a < n * n) {
                assert(k == diff(ans[0], a, n));
                ans[i] = a;
            } else {
                assert(n <= b && b < n * n);
                assert(k == diff(ans[0], b, n));
                ans[i] = b;
            }
            assert(k == diff(ans[0], ans[i], n));
        } else {
            assert(v.size() == 2);
            int i = v[0], j = v[1];
            // cerr << p << ' ' << q << ' ' << i << ' ' << j << endl;
            assert(n <= a && a < n * n);
            assert(n <= b && b < n * n);
            assert(a != b);
            assert(k == diff(ans[0], a, n));
            assert(k == diff(ans[0], b, n));
            if (diff(a, n, n) != diff(b, n, n)) {
                if (query(i, idx10) == diff(a, n, n)) {
                    ans[i] = a; ans[j] = b;
                } else {
                    ans[j] = a; ans[i] = b;
                }
            } else {
                assert(diff(a, n * n - 1, n) != diff(b, n * n - 1, n));
                if (query(i, idxnn) == diff(a, n * n - 1, n)) {
                    ans[i] = a; ans[j] = b;
                } else {
                    ans[j] = a; ans[i] = b;
                }
            }
        }
    }

    answer(ans);
}
0