Submission #721472

#	Time	Username	Problem	Language	Result	Execution time	Memory
721472		minhcool	The Big Prize (IOI17_prize)	C++17	94.11 / 100	76 ms	336 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
vector<int> askk(int pos){
	return ask(pos - 1);
}
 
int find_best(int N){
	n = N;
	if(n <= 5000){
		for(int i = 1; i <= n; i++){
			vector<int> res = askk(i);
			if(res[0] == 0 && res[1] == 0) return i - 1;
		}
	}
	//cout << "OK\n";
	int mx = -1;
  /*
	for(int i = 1; i <= 500; i++){
		vector<int> v = askk(rnd(1, n));
		mx = max(mx, v[0] + v[1]);
	}*/
	int itr = 0, tot = 0;
	while(1){
      if(itr >= n) return n - 1;
		int l = itr + 1, r = n;
        bool ck = 0;
		while(l < r){
			int mid = (l + r) >> 1;
            if(!ck) mid = min(l + 500, n);        
			vector<int> a = askk(mid);
            mx = max(mx, a[0] + a[1]);
			if(a[0] + a[1] != mx){
              r = mid;
              ck = 1;
            }
			else if(a[0] > tot){
              r = mid;
              ck = 1;
            }
			else l = mid + 1;
		}
		vector<int> v = askk(l);
		if(!(v[0] + v[1])) return l - 1;
		itr = l;
        tot++;
		/*
		assert(l != n);
		vector<int> v = ask(l + 1);
		assert(v[0] + v[1] != mx);
		if(!(v[0] + v[1])) return l + 1;
		int temp = l + 1;
		set<int> se;
		se.insert(mx);
		se.insert(v[0] + v[1]);*/
	}
}
 
 
/*
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
*/

Compilation message (stderr)

prize.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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