結果

問題 No.850 企業コンテスト2位
ユーザー もりをもりを
提出日時 2019-07-05 22:12:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,991 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 171,532 KB
実行使用メモリ 25,476 KB
平均クエリ数 241.82
最終ジャッジ日時 2024-07-16 17:21:32
合計ジャッジ時間 8,520 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 21 ms
25,476 KB
testcase_03 AC 21 ms
24,836 KB
testcase_04 AC 20 ms
24,580 KB
testcase_05 AC 21 ms
25,476 KB
testcase_06 AC 23 ms
24,964 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 21 ms
24,784 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