oj.uz

Submission #140382

# Submission time Handle Problem Language Result Execution time Memory
140382 2019-08-02T16:55:25 Z shashwatchandra The Big Prize (IOI17_prize) C++17
20 / 100
 99 ms 1148 KB 
#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 = N;
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++;
			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 3 ms 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1080 KB Output is correct
5 Correct 3 ms 1076 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 3 ms 1080 KB Output is correct
6 Correct 2 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 4 ms 1080 KB Output is correct
9 Correct 3 ms 1080 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 13 ms 1016 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 26 ms 1016 KB Output is correct
16 Incorrect 99 ms 1080 KB Incorrect
17 Halted 0 ms 0 KB -