oj.uz

Submission #1013381

# Submission time Handle Problem Language Result Execution time Memory
1013381 2024-07-03T13:29:17 Z NintsiChkhaidze The Big Prize (IOI17_prize) C++17
20 / 100
 73 ms 7008 KB 
#include <bits/stdc++.h>
#define pb push_back
#include "prize.h"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int B) {
	int y = rng();
	y = abs(y);
	return y % B;
}

bool fix[200003];
int Q;
vector <int> dp[200003];

vector <int> askk(int x){
	if (dp[x].size()) return dp[x];
	++Q;
// 	if (Q > 10000) assert(0);
	return dp[x] = ask(x);
}

int find_best(int n){
	
	int block = sqrt(n) + 1;
	int mxx=-1;
	while (1){
		vector <int> v;
		for (int j=0;j<n;j++){
			if (!fix[j]) v.pb(j);
		}
		
		int mx = -1,id = -1;
		vector <int> opt;
		
		int len = (int)v.size();
		for (int i = 0; i < min(len,block); i++){
			int x = v[i];
			vector <int> vec = askk(x);
			
			int sum = vec[0] + vec[1];
			if (sum == 0) return x;
			
			if (sum > mx){
				mx = sum;
				id = x;
				opt = vec;
			}
		}
//		if (len < block) assert(0);
		
		if (mxx != -1 && mx != mxx) assert(0);
		mxx=mx;
		
		int l = id + 1,r = n - 1,res = id;
		for (int i = id + 1; i < n; i++){
			if (fix[i]){
				r = i - 1;
				break;
			}
		}
		
		while (l <= r){
			int mid = (l + r) >> 1;
			vector <int> k = askk(mid);
			if (k[0] + k[1] == 0) return mid;
			if (k != opt){
				r = mid - 1;
			}else{
				res = mid;
				l = mid + 1;
			}
		}
		
//		cout<<id<<" -> "<<res<<endl;
		for (int i = id; i <= res; i++)	
			fix[i] = 1;
	}
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6096 KB Output is correct
2 Correct 5 ms 6096 KB Output is correct
3 Correct 4 ms 6096 KB Output is correct
4 Correct 4 ms 6096 KB Output is correct
5 Correct 5 ms 6280 KB Output is correct
6 Correct 2 ms 6092 KB Output is correct
7 Correct 5 ms 6096 KB Output is correct
8 Correct 4 ms 6096 KB Output is correct
9 Correct 3 ms 6096 KB Output is correct
10 Correct 7 ms 6096 KB Output is correct
11 Partially correct 41 ms 7008 KB Partially correct - number of queries: 6802
12 Correct 4 ms 6096 KB Output is correct
13 Incorrect 73 ms 6968 KB Incorrect
14 Halted 0 ms 0 KB -