結果

問題 No.850 企業コンテスト2位
コンテスト
ユーザー もりを
提出日時 2019-07-05 22:12:12
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 22
権限があれば一括ダウンロードができます

ソースコード

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