結果

問題 No.1306 Exactly 2 Digits
ユーザー t33ft33f
提出日時 2020-12-06 13:35:00
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,929 bytes
コンパイル時間 1,458 ms
コンパイル使用メモリ 124,980 KB
実行使用メモリ 25,836 KB
平均クエリ数 1018.09
最終ジャッジ日時 2024-07-17 09:56:18
合計ジャッジ時間 46,224 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 RE -
testcase_65 RE -
testcase_66 RE -
testcase_67 RE -
testcase_68 RE -
testcase_69 RE -
testcase_70 RE -
testcase_71 RE -
testcase_72 RE -
testcase_73 RE -
testcase_74 RE -
testcase_75 RE -
testcase_76 RE -
testcase_77 RE -
testcase_78 RE -
testcase_79 RE -
testcase_80 RE -
testcase_81 RE -
testcase_82 RE -
testcase_83 RE -
testcase_84 RE -
testcase_85 RE -
testcase_86 RE -
testcase_87 RE -
testcase_88 RE -
testcase_89 RE -
testcase_90 RE -
testcase_91 RE -
testcase_92 RE -
testcase_93 RE -
testcase_94 RE -
testcase_95 RE -
testcase_96 RE -
testcase_97 RE -
testcase_98 RE -
testcase_99 RE -
testcase_100 RE -
testcase_101 RE -
testcase_102 RE -
testcase_103 RE -
testcase_104 RE -
testcase_105 RE -
testcase_106 RE -
testcase_107 RE -
testcase_108 RE -
testcase_109 RE -
testcase_110 RE -
testcase_111 RE -
testcase_112 RE -
testcase_113 RE -
testcase_114 RE -
testcase_115 RE -
testcase_116 RE -
testcase_117 RE -
testcase_118 RE -
testcase_119 RE -
testcase_120 RE -
testcase_121 RE -
testcase_122 RE -
権限があれば一括ダウンロードができます

ソースコード

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) {
    ++qcount;
    assert(qcount <= (n * n - n) / 2 * 3);
    if (!interactive) {
        auto [p, q] = diff(ans[i], ans[j], n);
        cerr << "? " << i << ' ' << j << endl;
        cerr << p << ' ' << q << endl;
        return {p, q};
    } else {
        cout << "? " << i << ' ' << j << 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