oj.uz

Submission #1036257

# Submission time Handle Problem Language Result Execution time Memory
1036257 2024-07-27T07:11:48 Z Alihan_8 The Big Prize (IOI17_prize) C++17
20 / 100
 53 ms 5520 KB 
#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}


mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

int find_best(int n){
	vector <vector<int>> dp(n);
	
	auto f = [&](int j){
		if ( dp[j].empty() ){
			dp[j] = ask(j);
		}
		
		return dp[j];
	};
	
	int ans = -1;
	
	int K = rnd(0, n - 1);
	
	for ( int i = n - 1; i > K; i-- ){
		auto c = f(i);
		
		if ( c[0] + c[1] == 0 ){
			ans = i;
			
			return ans;
		}
		
		int l = K + 1, r = i;
		
		while ( l < r ){
			int m = (l + r) / 2;
			
			if ( f(m) != c ){
				l = m + 1;
			} else r = m;
		}
		
		i = l; 
	}
	
	for ( int i = 0; i <= K; i++ ){
		auto c = f(i);
		
		if ( c[0] + c[1] == 0 ){
			ans = i;
			
			return ans;
		}
		
		int l = i, r = K + 1;
		
		while ( l + 1 < r ){
			int m = (l + r) / 2;
			
			if ( f(m) != c ){
				r = m;
			} else l = m;
		}
		
		i = l; 
	}
	
	assert(false);
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 2 ms 5040 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 3 ms 4952 KB Output is correct
10 Correct 2 ms 4952 KB Output is correct
11 Correct 6 ms 5464 KB Output is correct
12 Correct 6 ms 5160 KB Output is correct
13 Correct 2 ms 4952 KB Output is correct
14 Correct 9 ms 1112 KB Output is correct
15 Correct 13 ms 5188 KB Output is correct
16 Correct 12 ms 4952 KB Output is correct
17 Partially correct 53 ms 5520 KB Partially correct - number of queries: 8603
18 Correct 2 ms 4952 KB Output is correct
19 Incorrect 52 ms 5444 KB Incorrect
20 Halted 0 ms 0 KB -