oj.uz

Submission #1028950

# Submission time Handle Problem Language Result Execution time Memory
1028950 2024-07-20T10:43:04 Z parsadox2 The Big Prize (IOI17_prize) C++17
20 / 100
 608 ms 4068 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n , cnt[N];
bool marked[N] , dead[N];

int Sq(int val)
{
	for(int i = 1 ; i <= val ; i++)  if(i * i >= val)
		return i;
	return val;
}

int Solve()
{
	int Q = 0;
	int sq = Sq(n);
	int mx = 0;
	for(int i = 0 ; i < min(n , sq + 10) ; i++)
	{
		Q++;
		auto now = ask(i);
		mx = max(mx , now[0] + now[1]);
	}
	for(int asd = 0 ; asd < mx ; asd++)
	{
		vector <int> all;
		int tmp = 0;
		for(int i = 0 ; i < n ; i++) if(!dead[i])
		{
			if(marked[i])
				tmp++;
			else
			{
				cnt[i] = tmp;
				all.push_back(i);
			}
		}
		int low = -1 , high = all.size();
		while(high - low > 1)
		{
			Q++;
			int mid = (low + high) >> 1;
			int id = all[mid];
			auto now = ask(id);
			//cout << low << " " << high << " " << mid << endl;
			if(now[0] + now[1] != mx)
			{
				//cout << id << "! " << endl;
				marked[id] = true;
				break;
			}
			now[0] -= cnt[id];
			if(now[0] != 0)
				high = mid;
			else
				low = mid;
			dead[id] = true;
		}
	}
	for(int i = 0 ; i < n ; i++)  if(marked[i])
	{
		Q++;
		auto now = ask(i);
		if(now[0] + now[1] == 0)
			return i;
	}
	return -1;
}

int find_best(int nn) {
	n = nn;
	if(n == 1)
		return 0;
	return Solve();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2096 KB Output is correct
2 Correct 4 ms 2000 KB Output is correct
3 Correct 4 ms 2256 KB Output is correct
4 Correct 5 ms 2256 KB Output is correct
5 Correct 6 ms 2000 KB Output is correct
6 Correct 5 ms 2000 KB Output is correct
7 Correct 3 ms 2256 KB Output is correct
8 Correct 3 ms 2000 KB Output is correct
9 Correct 4 ms 1996 KB Output is correct
10 Correct 5 ms 2000 KB Output is correct
11 Correct 60 ms 3340 KB Output is correct
12 Correct 43 ms 3380 KB Output is correct
13 Correct 36 ms 3348 KB Output is correct
14 Correct 32 ms 896 KB Output is correct
15 Partially correct 526 ms 3484 KB Partially correct - number of queries: 7910
16 Partially correct 514 ms 3564 KB Partially correct - number of queries: 8703
17 Partially correct 530 ms 3620 KB Partially correct - number of queries: 8374
18 Partially correct 519 ms 3484 KB Partially correct - number of queries: 8758
19 Partially correct 466 ms 3888 KB Partially correct - number of queries: 7827
20 Partially correct 227 ms 2088 KB Partially correct - number of queries: 5537
21 Partially correct 462 ms 3496 KB Partially correct - number of queries: 8388
22 Partially correct 351 ms 3548 KB Partially correct - number of queries: 6213
23 Correct 9 ms 3188 KB Output is correct
24 Correct 35 ms 3324 KB Output is correct
25 Partially correct 495 ms 3728 KB Partially correct - number of queries: 8438
26 Partially correct 487 ms 3516 KB Partially correct - number of queries: 8549
27 Correct 10 ms 3080 KB Output is correct
28 Partially correct 522 ms 3392 KB Partially correct - number of queries: 8639
29 Partially correct 371 ms 3496 KB Partially correct - number of queries: 7077
30 Partially correct 526 ms 3600 KB Partially correct - number of queries: 8662
31 Partially correct 475 ms 3760 KB Partially correct - number of queries: 8172
32 Correct 38 ms 3428 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 558 ms 3848 KB Partially correct - number of queries: 8350
35 Correct 20 ms 3188 KB Output is correct
36 Partially correct 606 ms 3648 KB Partially correct - number of queries: 8300
37 Correct 36 ms 3352 KB Output is correct
38 Correct 16 ms 3184 KB Output is correct
39 Partially correct 608 ms 3724 KB Partially correct - number of queries: 8408
40 Partially correct 457 ms 3628 KB Partially correct - number of queries: 7466
41 Partially correct 523 ms 3576 KB Partially correct - number of queries: 8549
42 Partially correct 564 ms 3528 KB Partially correct - number of queries: 8549
43 Partially correct 507 ms 3520 KB Partially correct - number of queries: 8258
44 Partially correct 464 ms 3452 KB Partially correct - number of queries: 8453
45 Partially correct 523 ms 3520 KB Partially correct - number of queries: 8343
46 Partially correct 456 ms 3440 KB Partially correct - number of queries: 8225
47 Partially correct 517 ms 3588 KB Partially correct - number of queries: 8399
48 Partially correct 489 ms 3740 KB Partially correct - number of queries: 8674
49 Partially correct 571 ms 3824 KB Partially correct - number of queries: 8261
50 Partially correct 529 ms 4068 KB Partially correct - number of queries: 8752
51 Partially correct 535 ms 3356 KB Partially correct - number of queries: 8463
52 Partially correct 529 ms 3488 KB Partially correct - number of queries: 8228
53 Correct 10 ms 3188 KB Output is correct
54 Partially correct 506 ms 3528 KB Partially correct - number of queries: 8461
55 Partially correct 499 ms 3660 KB Partially correct - number of queries: 8273
56 Partially correct 534 ms 3508 KB Partially correct - number of queries: 8759
57 Partially correct 547 ms 3488 KB Partially correct - number of queries: 8573
58 Partially correct 563 ms 3612 KB Partially correct - number of queries: 8604
59 Partially correct 559 ms 3460 KB Partially correct - number of queries: 8548
60 Partially correct 560 ms 3552 KB Partially correct - number of queries: 8500
61 Correct 13 ms 3268 KB Output is correct
62 Correct 17 ms 3188 KB Output is correct
63 Correct 12 ms 3152 KB Output is correct
64 Correct 12 ms 3212 KB Output is correct
65 Correct 41 ms 3132 KB Output is correct
66 Partially correct 560 ms 3344 KB Partially correct - number of queries: 5939
67 Partially correct 537 ms 3336 KB Partially correct - number of queries: 5436
68 Partially correct 462 ms 3272 KB Partially correct - number of queries: 5684
69 Partially correct 532 ms 3228 KB Partially correct - number of queries: 5922
70 Correct 353 ms 3612 KB Output is correct
71 Partially correct 561 ms 3488 KB Partially correct - number of queries: 9426
72 Correct 44 ms 3372 KB Output is correct
73 Partially correct 481 ms 3504 KB Partially correct - number of queries: 9293
74 Partially correct 479 ms 3572 KB Partially correct - number of queries: 9350
75 Correct 11 ms 3096 KB Output is correct
76 Partially correct 424 ms 3524 KB Partially correct - number of queries: 8058
77 Partially correct 512 ms 3664 KB Partially correct - number of queries: 8806
78 Correct 36 ms 3364 KB Output is correct
79 Correct 216 ms 3680 KB Output is correct
80 Partially correct 489 ms 3536 KB Partially correct - number of queries: 8840
81 Partially correct 502 ms 3952 KB Partially correct - number of queries: 8816
82 Partially correct 484 ms 3760 KB Partially correct - number of queries: 8716
83 Correct 11 ms 3188 KB Output is correct
84 Partially correct 437 ms 3816 KB Partially correct - number of queries: 7206
85 Partially correct 479 ms 3524 KB Partially correct - number of queries: 8700
86 Incorrect 25 ms 3092 KB Integer -1 violates the range [0, 199999]
87 Halted 0 ms 0 KB -