Submission #1048673

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1048673	2024-08-08T09:01:28 Z	pcc	The Big Prize (IOI17_prize)	C++17	20 / 100	16 ms	5580 KB

prize

#include "prize.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define pii pair<int,int>
#define fs first
#define sc second
mt19937 seed(time(NULL));
#define rnd(l,r) uniform_int_distribution<int>(l,r)(seed)

#ifdef LOCAL
const int lim = 3;
const int dt = 5;
#else
const int lim = 5000;
const int dt = 470;
#endif

const int mxn = 2e5+10;
pii dp[mxn];
int N;
int big = 1e9;
int ans = 0;
bool done = false;
int C = 0;
ordered_set<int> st;
pii rng;

pii req(int p){
	if(dp[p].fs != -1)return dp[p];
	C++;
	assert(C<=10000);
	auto re = ask(p);
	return (dp[p] = pii(re[0],re[1]));
}

int check(int p){
	auto re = req(p);
	if(!re.fs&&!re.sc)return 0;
	else if(N-re.fs-re.sc == big)return 2;
	else if(re.fs+re.sc == 1){
		if(re.fs == 1)rng.sc = p-1;
		else rng.sc = p+1;
	}
	else{
		st.insert(p);
		return 1;
	}
}

deque<pii> q;

void calc(){
	if(done)return;
	int l,r;
	if(rnd(0,1)){
		auto [a,b] = q.front();q.pop_front();
		l = a,r = b;
	}
	else{
		auto [a,b] = q.back();q.pop_back();
		l = a,r = b;
	}
	l = max(l,rng.fs);r = min(r,rng.sc);
	cerr<<"DFS: "<<l<<','<<r<<endl;
	while(l<=r){
		if(!check(l)){
			ans = l;
			done = true;
			return;
		}
		else if(check(l) == 1){
			l++;
		}
		else break;
	}
	while(l<=r){
		if(!check(r)){
			ans = r;
			done = true;
			return;
		}
		else if(check(r) == 1){
			r--;
		}
		else break;
	}
	if(l>=r)return;
	int cnt = req(r).fs+req(l).sc-(N-big);
	if(!cnt)return;
	cerr<<"CHECK: "<<l<<','<<r<<','<<cnt<<endl;
	assert(cnt>0);
	int mid = (l+r+1)>>1;
	if(check(mid) == 0){
		ans = mid;
		done = true;
		return;
	}
	if(l == r)return;
	if(l != mid)q.push_back(pii(l,mid));
	if(mid != r)q.push_back(pii(mid,r));
	return;
}

int find_best(int nn) {
	N = nn;
	int pt = 0;
	for(int i = 1;i*i<2e5;i++)pt = i;
	cerr<<pt<<endl;
	for(auto &i:dp)i = pii(-1,-1);
	if(N<=lim){
		for(int i = 0;i<N;i++){
			auto tmp = req(i);
			if(!tmp.fs&&!tmp.sc)return i;
		}
		assert(false);
		return 0;
	}
	vector<int> perm;
	for(int i = 0;i<N;i++)perm.push_back(i);
	shuffle(perm.begin(),perm.end(),seed);
	for(int i = 0;i<dt;i++){
		auto tmp = req(perm[i]);
		big = min(big,N-tmp.fs-tmp.sc);
		if(!tmp.fs&&!tmp.sc){
			return perm[i];
		}
	}
	cerr<<"BIG: "<<big<<endl;
	q.push_back(pii(0,N-1));
	rng = pii(0,N-1);
	while(!q.empty()&&!done)calc();
	if(!done)exit(0);
	return ans;
}

Compilation message

prize.cpp: In function 'int check(int)':
prize.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3024 KB	Output is correct
2	Correct	6 ms	3024 KB	Output is correct
3	Correct	6 ms	3024 KB	Output is correct
4	Correct	5 ms	3024 KB	Output is correct
5	Correct	6 ms	3024 KB	Output is correct
6	Correct	5 ms	3020 KB	Output is correct
7	Correct	7 ms	3024 KB	Output is correct
8	Correct	5 ms	3020 KB	Output is correct
9	Correct	5 ms	3024 KB	Output is correct
10	Correct	5 ms	3024 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3024 KB	Output is correct
2	Correct	6 ms	3024 KB	Output is correct
3	Correct	6 ms	3024 KB	Output is correct
4	Correct	6 ms	3024 KB	Output is correct
5	Correct	5 ms	3024 KB	Output is correct
6	Correct	5 ms	3024 KB	Output is correct
7	Correct	5 ms	3024 KB	Output is correct
8	Correct	6 ms	3024 KB	Output is correct
9	Correct	5 ms	3024 KB	Output is correct
10	Correct	6 ms	3024 KB	Output is correct
11	Runtime error	16 ms	5580 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-