結果

問題 No.850 企業コンテスト2位
ユーザー tarattata1tarattata1
提出日時 2019-07-06 15:24:08
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 1,785 bytes
コンパイル時間 1,034 ms
コンパイル使用メモリ 76,812 KB
実行使用メモリ 24,252 KB
平均クエリ数 200.11
最終ジャッジ日時 2023-09-23 17:46:33
合計ジャッジ時間 3,321 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
23,520 KB
testcase_01 AC 26 ms
23,784 KB
testcase_02 AC 24 ms
23,568 KB
testcase_03 AC 26 ms
23,496 KB
testcase_04 AC 26 ms
23,496 KB
testcase_05 AC 25 ms
23,532 KB
testcase_06 AC 26 ms
23,496 KB
testcase_07 AC 30 ms
24,204 KB
testcase_08 AC 32 ms
24,252 KB
testcase_09 AC 32 ms
23,328 KB
testcase_10 AC 37 ms
23,508 KB
testcase_11 AC 36 ms
23,604 KB
testcase_12 AC 35 ms
23,784 KB
testcase_13 AC 35 ms
23,496 KB
testcase_14 AC 35 ms
23,916 KB
testcase_15 AC 35 ms
24,180 KB
testcase_16 AC 34 ms
24,060 KB
testcase_17 AC 36 ms
24,180 KB
testcase_18 AC 35 ms
23,964 KB
testcase_19 AC 35 ms
23,952 KB
testcase_20 AC 36 ms
23,316 KB
testcase_21 AC 36 ms
23,604 KB
testcase_22 AC 36 ms
23,232 KB
testcase_23 AC 37 ms
23,400 KB
testcase_24 AC 36 ms
23,352 KB
testcase_25 AC 36 ms
23,784 KB
testcase_26 AC 36 ms
23,532 KB
testcase_27 AC 26 ms
23,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);

    vector<int> a(n, -1);   // 各人が負けた相手を記録
    vector<int> b;      // 勝ち残った人たち

    int i,j;
    for(i=0; i<n; i++) b.push_back(i);

    for(i=0; i<10; i++) {
        if(b.size()==1) break;

        vector<int> c;
        int siz=(int)b.size();
        for(j=0; j<siz; j+=2) {
            if(j==siz-1) {
                c.push_back(b[j]);
            }
            else {
                printf("? %d %d\n", b[j]+1, b[j+1]+1);
                fflush(stdout);
                int ans;
                scanf("%d", &ans);
                if(ans==b[j]+1) {
                    c.push_back(b[j]);
                    a[b[j+1]]=b[j];
                }
                else {
                    c.push_back(b[j+1]);
                    a[b[j]]=b[j+1];
                }
            }
        }
        b.swap(c);
    }

    vector<int> d;
    int win = b[0];
    for(i=0; i<n; i++) {
        if(a[i]==win) d.push_back(i);
    }

    int sec=d[0];
    for(i=1; i<(int)d.size(); i++) {
        printf("? %d %d\n", sec+1, d[i]+1);
        fflush(stdout);
        int ans;
        scanf("%d", &ans);
        if(ans!=sec+1) {
            sec = d[i];
        }
    }
    printf("! %d\n", sec+1);

    return 0;
}
0