首页 > 其他 > 详细

Codeforces Round #503 (by SIS, Div. 2) D. The hat

时间:2018-08-16 00:30:13      阅读:195      评论:0      收藏:0      [点我收藏+]

技术分享图片

有图可以直观发现,如果一开始的pair(1,1+n/2)和pair(x, x+n/2)大小关系不同
那么中间必然存在一个答案

简单总结就是大小关系不同,中间就有答案
所以就可以使用二分

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;


int main() {
    int n;
    while(~scanf("%d", &n)) {
        printf("? 1\n");
        fflush(stdout);
        int t1; scanf("%d", &t1);

        printf("? %d\n", 1 + n/2);
        fflush(stdout);
        int t2; scanf("%d", &t2);

        bool flag = t1 > t2;
        if(t1 == t2) {
            printf("! 1\n");
            fflush(stdout);
            continue;
        }

        if(n == 2) {
            printf("! -1\n");
            fflush(stdout);
            continue;
        }

        int l = 1; int r = 1+n/2;

        bool success = false;
        while(l < r - 1) {
            int mid = (l + r) >>1;
            int mid2 = mid + n/2;

            printf("? %d\n", mid);
            fflush(stdout);
            int t1; scanf("%d", &t1);

            printf("? %d\n", mid2);
            fflush(stdout);
            int t2; scanf("%d", &t2);

            if(t1 == t2) {
                success = true;
                printf("! %d\n", mid);
                fflush(stdout);
                break;
            }
            if( (t1 < t2) ^ flag) l = mid;
            else r = mid;
        }

        if(!success) {
            printf("! -1\n");
            fflush(stdout);
        }
    }
    return 0;
}

Codeforces Round #503 (by SIS, Div. 2) D. The hat

原文:https://www.cnblogs.com/Basasuya/p/9484616.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!