Submission #252480

#	Time	Username	Problem	Language	Result	Execution time	Memory
252480		Mercenary	The Big Prize (IOI17_prize)	C++14	100 / 100	72 ms	9976 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef pair<int,int> ii;
#define mp make_pair
int ans = -1;
set<ii> s[maxn];

void solve(int l , int r){
    if(ans != -1 || l > r)return;
    int mid = l + r >> 1;
    vector<int> a = ask(mid);
    int sum = a[0] + a[1];
    if(sum == 0){
        ans = mid;
        return;
    }
    s[sum].insert(make_pair(mid,a[0]));
    auto it = s[sum].lower_bound(make_pair(mid,0));
    bool ok = 1 , ok1 = 1;
    if(next(it) != s[sum].end()){
        if((next(it)->second == a[0]))ok = 0;
    }
    if(it != s[sum].begin()){
        if((prev(it)->second == a[0]))ok1 = 0;
    }
    if(ok)solve(mid + 1 , r);
    if(ok1)solve(l , mid - 1);
}

int find_best(int n) {
	solve(0 , n - 1);
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void solve(int, int)':
prize.cpp:12:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80