CodeChef - ELHIDARR Find an element in hidden array（互动题）题解 - Java

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：有一串不递减的串，串中的任意元素都有k个，除了一个元素，他只有1 <= n < k-1个，你现在能向oj做出以下操作：

输出：1 pos，oj会返回pos位置的元素值

输出：2 val，回答那个特殊的元素是什么值

要求不能询问超过60次，给出特殊元素的值。

思路：先第一次二分找出k。可以想出，k * m和k * m + 1如果不同，那么k * m之前的数肯定没有特殊元素，反之则有，那么我们就找出第一个k * m == k * m + 1的地方，这之前的元素就是特殊元素。

每次printf之后都要加一句fflsh(stdout)，否则TLE伺候。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn = 1e5 + ;

const int MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

int val[maxn];

bool vis[maxn];

int T, n, k;

int get(int pos){

    if(pos > n || pos < ) return -;

    if(!vis[pos]){

        int b;

        printf("1 %d\n", pos);

        fflush(stdout);

        scanf("%d", &b);

        val[pos] = b;

        return b;

    }

    else{

        return val[pos];

    }

}

int main(){

    scanf("%d", &T);

    while(T--){

       memset(vis, false, sizeof(vis));

       scanf("%d", &n);

       int a, b;

       a = get();

       int l = , r = n, ans;

       while(l <= r){

            int m = (l + r) >> ;

            int c = get(m);

            if(c == a) ans = m;

            if(c != a) r = m - ;

            else l = m + ;

       }

       k = ans;

       if(get(k + ) == get( * k + )){

            printf("2 %d\n", get());

            fflush(stdout);

       }

       else{

            l = , r = n / k + ;

            while(l <= r){

                int m = (l + r) >> ;

                if(get(k * m) != get(k * m + )){

                    l = m + ;

                    ans = m + ;

                }

                else{

                    r = m - ;

                }

            }

            printf("2 %d\n", get((ans - ) * k + ));

            fflush(stdout);

       }

    }

    return ;

}