oj.uz

Submission #136010

# Submission time Handle Problem Language Result Execution time Memory
136010 2019-07-24T15:23:11 Z JustasZ The Big Prize (IOI17_prize) C++14
20 / 100
 109 ms 504 KB 
#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/*vector<int> ask(int i)
{
	cout << "? " << i << endl;
	vector<int>a(2);
	cin >> a[0] >> a[1];
	return a;
}*/
int find_best(int n)
{
	vector<int>a;
	if(n < 5000)
	{
		for(int i = 0; i < n; i++)
		{
			a = ask(i);
			if(a[0] == 0 && a[1] == 0)
				return i;
		}
	}
	int mx = 0;
	for(int it = 0; it < 5; it++)
	{
		int p = rd() % n;
		a = ask(p);
		mx = max(mx, a[0] + a[1]);
	}
	int cnt = 5;
	int i = 0;
	while(i < n)
	{
		//assert(++cnt < 10000);
		a = ask(i);
		if(a[0] + a[1] == 0)
			return i;
		vector<int>nex = ask(i + 1);
		if(nex[0] + nex[1] != mx)
		{
			++i;
			continue;
		}
		if(a[0] + a[1] == mx)
		{
			int fi = a[0], se = a[1];
			int l = i + 1, r = n - se;
			while(l < r)
			{
				int mid = (l + r) / 2;
				//assert(++cnt < 10000);
				a = ask(mid);
				if(a[0] + a[1] != mx)
					r = mid;
				else
				{
					if(a[0] > fi)
						r = mid - 1;
					else
						l = mid + 1;
				}
			}
			//assert(++cnt < 10000);
			a = ask(l);
			//assert(a[0] + a[1] != mx);
			if(a[0] + a[1] == 0)
				return l;
			i = l + 1;
		}
		else 
			i++;
	}
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:43:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 5;
      ^~~
prize.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 416 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 312 KB Output is correct
10 Correct 2 ms 248 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 316 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 396 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 4 ms 296 KB Output is correct
12 Correct 2 ms 308 KB Output is correct
13 Correct 5 ms 312 KB Output is correct
14 Correct 5 ms 248 KB Output is correct
15 Correct 8 ms 312 KB Output is correct
16 Partially correct 39 ms 308 KB Partially correct - number of queries: 7486
17 Correct 2 ms 376 KB Output is correct
18 Partially correct 65 ms 376 KB Partially correct - number of queries: 8793
19 Correct 2 ms 316 KB Output is correct
20 Correct 13 ms 400 KB Output is correct
21 Correct 32 ms 308 KB Output is correct
22 Correct 8 ms 316 KB Output is correct
23 Correct 2 ms 248 KB Output is correct
24 Correct 2 ms 308 KB Output is correct
25 Correct 26 ms 396 KB Output is correct
26 Correct 49 ms 312 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Partially correct 49 ms 312 KB Partially correct - number of queries: 8365
29 Partially correct 59 ms 376 KB Partially correct - number of queries: 6328
30 Partially correct 49 ms 312 KB Partially correct - number of queries: 8728
31 Correct 2 ms 248 KB Output is correct
32 Correct 6 ms 316 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 28 ms 308 KB Output is correct
35 Correct 4 ms 248 KB Output is correct
36 Correct 23 ms 248 KB Output is correct
37 Correct 3 ms 376 KB Output is correct
38 Correct 2 ms 248 KB Output is correct
39 Correct 23 ms 248 KB Output is correct
40 Partially correct 74 ms 376 KB Partially correct - number of queries: 7451
41 Partially correct 56 ms 248 KB Partially correct - number of queries: 5258
42 Partially correct 52 ms 248 KB Partially correct - number of queries: 5258
43 Correct 48 ms 308 KB Output is correct
44 Correct 41 ms 248 KB Output is correct
45 Correct 20 ms 424 KB Output is correct
46 Correct 2 ms 248 KB Output is correct
47 Correct 36 ms 392 KB Output is correct
48 Partially correct 37 ms 312 KB Partially correct - number of queries: 6497
49 Correct 5 ms 376 KB Output is correct
50 Partially correct 103 ms 376 KB Partially correct - number of queries: 8794
51 Correct 28 ms 376 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 3 ms 400 KB Output is correct
54 Correct 21 ms 308 KB Output is correct
55 Correct 2 ms 248 KB Output is correct
56 Partially correct 45 ms 504 KB Partially correct - number of queries: 8788
57 Partially correct 46 ms 248 KB Partially correct - number of queries: 6412
58 Partially correct 34 ms 376 KB Partially correct - number of queries: 6517
59 Partially correct 63 ms 248 KB Partially correct - number of queries: 5258
60 Correct 26 ms 308 KB Output is correct
61 Correct 3 ms 376 KB Output is correct
62 Correct 2 ms 248 KB Output is correct
63 Correct 3 ms 248 KB Output is correct
64 Correct 3 ms 248 KB Output is correct
65 Correct 3 ms 380 KB Output is correct
66 Correct 10 ms 248 KB Output is correct
67 Correct 2 ms 376 KB Output is correct
68 Correct 10 ms 248 KB Output is correct
69 Correct 10 ms 376 KB Output is correct
70 Correct 2 ms 424 KB Output is correct
71 Partially correct 90 ms 248 KB Partially correct - number of queries: 8811
72 Correct 9 ms 248 KB Output is correct
73 Partially correct 45 ms 376 KB Partially correct - number of queries: 8671
74 Partially correct 60 ms 376 KB Partially correct - number of queries: 8713
75 Correct 4 ms 248 KB Output is correct
76 Partially correct 78 ms 248 KB Partially correct - number of queries: 7456
77 Partially correct 62 ms 244 KB Partially correct - number of queries: 8848
78 Correct 9 ms 248 KB Output is correct
79 Correct 42 ms 296 KB Output is correct
80 Partially correct 48 ms 504 KB Partially correct - number of queries: 8822
81 Partially correct 47 ms 376 KB Partially correct - number of queries: 8846
82 Partially correct 82 ms 248 KB Partially correct - number of queries: 8773
83 Correct 4 ms 248 KB Output is correct
84 Partially correct 73 ms 248 KB Partially correct - number of queries: 7225
85 Partially correct 89 ms 248 KB Partially correct - number of queries: 8862
86 Incorrect 109 ms 248 KB Incorrect
87 Halted 0 ms 0 KB -