Submission #140384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140384	2019-08-02T16:56:58 Z	shashwatchandra	The Big Prize (IOI17_prize)	C++17	20 / 100	77 ms	1272 KB

prize

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

#define REP(i,n) for(int i = 0;i < n;i++)
#define RE(i,n) for(int i = 1;i <= n;i++)

const int N = 2e5+1;

int blocksize = 501;
int block[N];
int blockstart[N];

int find_best(int n) {
	int curblock = 1;
	int cursize = 0;
	blockstart[1] = 0;
	for(int i = 0;i < n;i++){
		block[i] = curblock;
		cursize++;
		if(cursize == blocksize){
			curblock++;
			cursize = 0;
			blockstart[curblock] = i+1;
		}
	}
	int i = 0;
	while(i < n){
		int lo = i;
		int hi = min(n-1,blockstart[block[i]]+blocksize-1);
		vector<int> res = ask(i);
		if(!(res[0]+res[1]))return i;
		while(lo < hi){
			int mid = (lo+hi+1)/2;
			vector<int> wow = ask(mid);
			if(wow == res)lo = mid;
			else hi = mid-1;
		}
		i = lo+1;
	}
	return 0;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1016 KB	Output is correct
2	Correct	26 ms	1016 KB	Output is correct
3	Correct	13 ms	1144 KB	Output is correct
4	Correct	42 ms	1064 KB	Output is correct
5	Correct	24 ms	1020 KB	Output is correct
6	Correct	3 ms	1148 KB	Output is correct
7	Correct	18 ms	1144 KB	Output is correct
8	Correct	27 ms	1144 KB	Output is correct
9	Correct	13 ms	1144 KB	Output is correct
10	Correct	35 ms	1016 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1016 KB	Output is correct
2	Correct	22 ms	1272 KB	Output is correct
3	Correct	18 ms	1020 KB	Output is correct
4	Correct	40 ms	1144 KB	Output is correct
5	Correct	14 ms	1080 KB	Output is correct
6	Correct	3 ms	1080 KB	Output is correct
7	Correct	15 ms	1084 KB	Output is correct
8	Correct	27 ms	1016 KB	Output is correct
9	Correct	13 ms	1160 KB	Output is correct
10	Correct	37 ms	1016 KB	Output is correct
11	Correct	24 ms	1016 KB	Output is correct
12	Correct	4 ms	1016 KB	Output is correct
13	Correct	49 ms	1080 KB	Output is correct
14	Correct	7 ms	376 KB	Output is correct
15	Correct	21 ms	1016 KB	Output is correct
16	Partially correct	77 ms	1160 KB	Partially correct - number of queries: 9923
17	Correct	3 ms	1016 KB	Output is correct
18	Incorrect	73 ms	1272 KB	Incorrect
19	Halted	0 ms	0 KB	-