oj.uz

Submission #721443

# Submission time Handle Problem Language Result Execution time Memory
721443 2023-04-11T01:40:14 Z minhcool The Big Prize (IOI17_prize) C++17
20 / 100
 86 ms 300 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

vector<int> askk(int pos){
	return ask(pos - 1);
}

int find_best(int N){
	n = N;
	if(n <= 5000){
		for(int i = 1; i <= n; i++){
			vector<int> res = askk(i);
			if(res[0] == 0 && res[1] == 0) return i - 1;
		}
	}
	//cout << "OK\n";
	int mx = -1;
	for(int i = 1; i <= 5; i++){
		vector<int> v = askk(rnd(1, n));
		mx = max(mx, v[0] + v[1]);
	}
	int itr = 0, tot = 0;
	while(1){
		int l = itr + 1, r = n;
		while(l < r){
			int mid = (l + r) >> 1;
			vector<int> a = askk(mid);
			if(a[0] + a[1] != mx) r = mid;
			else if(a[0] > tot) r = mid;
			else l = mid + 1;
		}
		vector<int> v = askk(l);
		if(!(v[0] + v[1])) return l - 1;
		itr = l;
		/*
		assert(l != n);
		vector<int> v = ask(l + 1);
		assert(v[0] + v[1] != mx);
		if(!(v[0] + v[1])) return l + 1;
		int temp = l + 1;
		set<int> se;
		se.insert(mx);
		se.insert(v[0] + v[1]);*/
	}
}


/*
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
*/

Compilation message

prize.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 284 KB Output is correct
9 Correct 1 ms 276 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Incorrect 86 ms 208 KB Incorrect
12 Halted 0 ms 0 KB -