Submission #1048225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1048225	2024-08-08T05:38:18 Z	pcc	The Big Prize (IOI17_prize)	C++17	20 / 100	94 ms	2136 KB

prize

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

#define pii pair<int,int>
#define fs first
#define sc second

#ifdef LOCAL
const int lim = 3;
const int sq = 5;
#else
const int lim = 5000;
const int sq = 500;
#endif

const int mxn = 2e5+10;
pii dp[mxn];
int N;
int big = 1e9;
int ans = 0;
bool done = false;

pii req(int p){
	if(dp[p].fs != -1)return dp[p];
	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 return 1;
}

void dfs(int l,int r){
	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;
	if(done)return;
	cerr<<"CHECK: "<<l<<','<<r<<','<<cnt<<endl;
	assert(cnt>0);
	int mid = (l+r)>>1;
	if(check(mid) == 0){
		ans = mid;
		done = true;
		return;
	}
	if(l == r)return;
	int ml = mid-1,mr = mid+1;
	while(ml>=l){
		if(check(ml) == 0){
			ans = ml;
			done = true;
			return;
		}
		else if(check(ml) == 1){
			ml--;
		}
		else break;
	}
	while(mr<=r){
		if(check(mr) == 0){
			ans = mr;
			done = true;
			return;
		}
		else if(check(mr) == 1){
			mr++;
		}
		else break;
	}
	if(ml>l){
		int tmp = req(ml).fs+req(l).sc-(N-big);
		assert(tmp>=0);
		if(tmp)dfs(l,ml);
	}
	if(mr<r){
		int tmp = req(mr).sc+req(r).fs-(N-big);
		assert(tmp>=0);
		if(tmp)dfs(mr,r);
	}
	return;
}

int find_best(int nn) {
	N = nn;
	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;
	}
	for(int i = 0;i<sq;i++){
		auto tmp = req(i);
		big = min(big,N-tmp.fs-tmp.sc);
	}
	cerr<<"BIG: "<<big<<endl;
	dfs(0,N-1);
	assert(done);
	return ans;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1880 KB	Output is correct
2	Correct	3 ms	2000 KB	Output is correct
3	Correct	2 ms	1876 KB	Output is correct
4	Correct	3 ms	1880 KB	Output is correct
5	Correct	3 ms	1880 KB	Output is correct
6	Correct	3 ms	2136 KB	Output is correct
7	Correct	4 ms	1880 KB	Output is correct
8	Correct	3 ms	1880 KB	Output is correct
9	Correct	4 ms	1880 KB	Output is correct
10	Correct	3 ms	1880 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1880 KB	Output is correct
2	Correct	3 ms	1880 KB	Output is correct
3	Correct	4 ms	2004 KB	Output is correct
4	Correct	2 ms	1880 KB	Output is correct
5	Correct	2 ms	1880 KB	Output is correct
6	Correct	2 ms	1880 KB	Output is correct
7	Correct	2 ms	1880 KB	Output is correct
8	Correct	3 ms	1880 KB	Output is correct
9	Correct	3 ms	2136 KB	Output is correct
10	Correct	3 ms	1880 KB	Output is correct
11	Correct	6 ms	2136 KB	Output is correct
12	Correct	4 ms	2004 KB	Output is correct
13	Correct	12 ms	2136 KB	Output is correct
14	Correct	5 ms	2000 KB	Output is correct
15	Correct	13 ms	2016 KB	Output is correct
16	Partially correct	94 ms	2136 KB	Partially correct - number of queries: 8993
17	Correct	3 ms	1880 KB	Output is correct
18	Incorrect	81 ms	2104 KB	Incorrect
19	Halted	0 ms	0 KB	-