oj.uz

Submission #64606

# Submission time Handle Problem Language Result Execution time Memory
64606 2018-08-05T03:25:45 Z nvmdava The Big Prize (IOI17_prize) C++17
20 / 100
 160 ms 6272 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
 
 
vector<int> ans[210000];
int mx = -1, s = -1, L, R;

void find(int l, int r){
	if(s != -1 || r < L || l > R){
		return;
	}
	int m = (l + r) >> 1;
	ans[m] = ask(m);
	if(ans[m][0] == 0){
		if(ans[m][1] == 0){
			s = m;
			return;
		}
		L = m + 1;
	}
	if(ans[m][1] == 0){
		R = m - 1;
	}
	if(ans[m][0] == ans[l][0]){
		find(m, r);
	} else if(ans[m][1] == ans[r][1]){
		find(l, m);
	} else {
		find(l, m);
		find(m, r);
	}
}

int find_best(int n) {
	L = 0;
	R = n - 1;
	ans[0] = ask(0);
	ans[n - 1] = ask(n - 1);
	
	if(ans[0][0] + ans[0][1] == 0){
		return 0;
	}
	if(ans[n - 1][0] + ans[n - 1][1] == 0){
		return n - 1;
	}
	find(0, n - 1);
	return s;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5224 KB Output is correct
2 Correct 9 ms 5300 KB Output is correct
3 Correct 8 ms 5464 KB Output is correct
4 Correct 9 ms 5464 KB Output is correct
5 Correct 8 ms 5464 KB Output is correct
6 Correct 9 ms 5464 KB Output is correct
7 Correct 11 ms 5464 KB Output is correct
8 Correct 10 ms 5464 KB Output is correct
9 Correct 10 ms 5472 KB Output is correct
10 Correct 15 ms 5472 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5472 KB Output is correct
2 Correct 10 ms 5472 KB Output is correct
3 Correct 8 ms 5472 KB Output is correct
4 Correct 9 ms 5520 KB Output is correct
5 Correct 9 ms 5520 KB Output is correct
6 Correct 9 ms 5520 KB Output is correct
7 Correct 7 ms 5520 KB Output is correct
8 Correct 9 ms 5520 KB Output is correct
9 Correct 9 ms 5520 KB Output is correct
10 Correct 6 ms 5520 KB Output is correct
11 Incorrect 160 ms 6272 KB Incorrect
12 Halted 0 ms 0 KB -