結果

問題 No.282 おもりと天秤(2)
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-06-14 18:50:28
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,032 bytes
コンパイル時間 1,890 ms
コンパイル使用メモリ 182,808 KB
実行使用メモリ 25,220 KB
平均クエリ数 24.04
最終ジャッジ日時 2024-07-16 23:57:48
合計ジャッジ時間 11,280 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
24,580 KB
testcase_01 AC 35 ms
25,220 KB
testcase_02 AC 27 ms
24,964 KB
testcase_03 AC 26 ms
24,580 KB
testcase_04 AC 25 ms
24,836 KB
testcase_05 AC 30 ms
24,836 KB
testcase_06 AC 37 ms
25,220 KB
testcase_07 AC 26 ms
24,836 KB
testcase_08 AC 41 ms
25,208 KB
testcase_09 AC 24 ms
24,836 KB
testcase_10 AC 1,754 ms
24,580 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    int N;
    void input() {
        cin >> N;
    }

    void solve() {
        vector<vector<int>> F(N, vector<int>(N, -5));
        queue<pair<int, int>> Q;
        vector<pair<int, int>> vs;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                vs.push_back(make_pair(i, j));
            }
        }
        random_shuffle(vs.begin(), vs.end());
        for (int i = 0; i < vs.size(); i++) Q.push(vs[i]);
        while (not Q.empty()) {
            cout << "?";
            vector<bool> used(N, false);
            vector<pair<int, int>> V;
            set<pair<int,int>> S;
            for (int i = 0; V.size() < N && not Q.empty(); i++) {
                auto p = Q.front(); Q.pop();
                int a = p.first;
                int b = p.second;
                if (S.count(p)) {
                    Q.push(p);
                    break;
                }
                S.insert(p);
                if (used[a] || used[b]) {
                    Q.push(p);
                } else {
                    cout << " " << a+1 << " " << b+1;
                    used[a] = used[b] = true;
                    V.push_back(p);
                }
            }
            for (int i = V.size(); i < N; i++) {
                cout << " 0 0";
            }
            cout << endl;

            vector<char> C(N, '?');
            cin >> C;
            for (int i = 0; i < min(N, int(V.size())); i++) {
                int a = V[i].first;
                int b = V[i].second;
                if (C[i] == '>') {
                    F[a][b] = 1;
                    F[b][a] = -1;
                } else if (C[i] == '=') {
                    F[a][b] = 0;
                    F[b][a] = 0;
                } else {
                    assert(C[i] == '<');
                    F[a][b] = -1;
                    F[b][a] = 1;
                }
            }
            /*
            for (int i = 0; i < N; i++) {
                cout << F[i] << endl;
            }
            */
        }

        vector<pair<int,int>> xs;
        for (int i = 0; i < N; i++) {
            int c = 0;
            for (int j = 0; j < N; j++) {
                c += (F[i][j] == 1);
            }
            xs.push_back(make_pair(c, i));
        }
        sort(xs.begin(), xs.end());
        cout << "!";
        for (int i = 0; i < N; i++) {
            cout << " " << xs[i].second + 1;
        }
        cout << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}
0