結果

問題 No.850 企業コンテスト2位
ユーザー もりをもりを
提出日時 2019-07-05 22:12:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,991 bytes
コンパイル時間 1,481 ms
コンパイル使用メモリ 170,908 KB
実行使用メモリ 24,336 KB
平均クエリ数 241.82
最終ジャッジ日時 2023-09-23 17:28:35
合計ジャッジ時間 7,415 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 25 ms
23,388 KB
testcase_03 AC 24 ms
23,940 KB
testcase_04 AC 26 ms
23,352 KB
testcase_05 AC 24 ms
23,544 KB
testcase_06 AC 23 ms
23,928 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 25 ms
23,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);++(i))
#define EACH(e,v) for(auto& e:v)
#define ALL(v) (v).begin(),(v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort((v).rbegin(),(v).rend())
#define PERM(v) SORT(v);for(bool c##p=1;c##p;c##p=next_permutation(ALL(v)))
#define UNIQUE(v) SORT(v);(v).erase(unique(ALL(v)),(v).end())
template<typename A,typename B> inline bool chmax(A &a,const B &b){if(a<b){a=b;return 1;}return 0;}
template<typename A,typename B> inline bool chmin(A &a,const B &b){if(a>b){a=b;return 1;}return 0;}

const int MOD = (int)1e9 + 7;
const int INF = 1 << 30;
const ll INFF = 1LL << 62;

// 下にy, 右にx
enum {R, U, L, D};
const int dx[] = {1,  0, -1, 0};
const int dy[] = {0, -1,  0, 1};

struct match {
    int x, y;
    bool x_win;
};

signed main() {

    int N;
    cin >> N;

    // 1 - indexed
    vector<int> wincnt(N + 1, 0), losecnt(N + 1, 0);
    vector<match> result;

    int cnt = 0;

    for (int i = 1; i <= N - 1; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (cnt == 334) break;
            if (losecnt[j] > 2) continue;
            // i vs j
            cout << "? " << i << ' ' << j << endl;  ++cnt;
            int ans;    cin >> ans;
            result.emplace_back((match){i, j, ans == i});
            if (ans == i) {
                wincnt[i]++;
                losecnt[j]++;
            } else {
                losecnt[i]++;
                wincnt[j]++;
                if (losecnt[i] > 2) break;
            }
        }
    }

    int mx = *max_element(wincnt.begin(), wincnt.end());
    int mx_tmp = -1;
    int sec = -1;
    FOR(i, 1, N + 1) {
        if (mx == wincnt[i]) continue;
        if (chmax(mx_tmp, wincnt[i])) sec = i;
    }
    cout << "! " << sec << endl;

    // FOR(i, 1, N + 1) cout <<  wincnt[i] << " \n"[i == N];
    // FOR(i, 1, N + 1) cout << losecnt[i] << " \n"[i == N];

}
0