oj.uz

Submission #1028769

# Submission time Handle Problem Language Result Execution time Memory
1028769 2024-07-20T08:26:15 Z parsadox2 The Big Prize (IOI17_prize) C++17
90 / 100
 600 ms 4108 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 + 100) ; 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 4 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 4 ms 2000 KB Output is correct
5 Correct 4 ms 2256 KB Output is correct
6 Correct 3 ms 2000 KB Output is correct
7 Correct 5 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 3 ms 2100 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2000 KB Output is correct
2 Correct 4 ms 2000 KB Output is correct
3 Correct 4 ms 2000 KB Output is correct
4 Correct 4 ms 2000 KB Output is correct
5 Correct 4 ms 2000 KB Output is correct
6 Correct 6 ms 2000 KB Output is correct
7 Correct 6 ms 2000 KB Output is correct
8 Correct 5 ms 2000 KB Output is correct
9 Correct 3 ms 2256 KB Output is correct
10 Correct 3 ms 2000 KB Output is correct
11 Correct 43 ms 3428 KB Output is correct
12 Correct 42 ms 3336 KB Output is correct
13 Correct 52 ms 3392 KB Output is correct
14 Correct 22 ms 772 KB Output is correct
15 Partially correct 561 ms 3888 KB Partially correct - number of queries: 8000
16 Partially correct 573 ms 3604 KB Partially correct - number of queries: 8793
17 Partially correct 600 ms 4108 KB Partially correct - number of queries: 8464
18 Partially correct 527 ms 3716 KB Partially correct - number of queries: 8848
19 Partially correct 511 ms 3712 KB Partially correct - number of queries: 7917
20 Partially correct 201 ms 2068 KB Partially correct - number of queries: 5627
21 Partially correct 586 ms 3348 KB Partially correct - number of queries: 8478
22 Partially correct 404 ms 3468 KB Partially correct - number of queries: 6303
23 Correct 12 ms 3188 KB Output is correct
24 Correct 42 ms 3296 KB Output is correct
25 Partially correct 552 ms 3452 KB Partially correct - number of queries: 8528
26 Partially correct 532 ms 3600 KB Partially correct - number of queries: 8639
27 Correct 12 ms 3236 KB Output is correct
28 Partially correct 551 ms 3908 KB Partially correct - number of queries: 8729
29 Partially correct 446 ms 3908 KB Partially correct - number of queries: 7167
30 Partially correct 573 ms 3488 KB Partially correct - number of queries: 8752
31 Partially correct 556 ms 3696 KB Partially correct - number of queries: 8262
32 Correct 44 ms 3416 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 537 ms 3484 KB Partially correct - number of queries: 8440
35 Correct 20 ms 3232 KB Output is correct
36 Partially correct 543 ms 3528 KB Partially correct - number of queries: 8390
37 Correct 37 ms 3380 KB Output is correct
38 Correct 12 ms 3188 KB Output is correct
39 Partially correct 501 ms 3456 KB Partially correct - number of queries: 8498
40 Partially correct 455 ms 3688 KB Partially correct - number of queries: 7556
41 Partially correct 570 ms 3596 KB Partially correct - number of queries: 8639
42 Partially correct 552 ms 3720 KB Partially correct - number of queries: 8639
43 Partially correct 513 ms 3432 KB Partially correct - number of queries: 8348
44 Partially correct 527 ms 3436 KB Partially correct - number of queries: 8543
45 Partially correct 526 ms 3536 KB Partially correct - number of queries: 8433
46 Partially correct 561 ms 3832 KB Partially correct - number of queries: 8315
47 Partially correct 548 ms 3856 KB Partially correct - number of queries: 8489
48 Partially correct 530 ms 3516 KB Partially correct - number of queries: 8764
49 Partially correct 573 ms 3744 KB Partially correct - number of queries: 8351
50 Partially correct 595 ms 3504 KB Partially correct - number of queries: 8842
51 Partially correct 564 ms 3816 KB Partially correct - number of queries: 8553
52 Partially correct 558 ms 3652 KB Partially correct - number of queries: 8318
53 Correct 12 ms 3180 KB Output is correct
54 Partially correct 574 ms 3828 KB Partially correct - number of queries: 8551
55 Partially correct 549 ms 3744 KB Partially correct - number of queries: 8363
56 Partially correct 518 ms 3488 KB Partially correct - number of queries: 8849
57 Partially correct 545 ms 3688 KB Partially correct - number of queries: 8663
58 Partially correct 520 ms 3692 KB Partially correct - number of queries: 8694
59 Partially correct 521 ms 4076 KB Partially correct - number of queries: 8638
60 Partially correct 499 ms 3768 KB Partially correct - number of queries: 8590
61 Correct 12 ms 3116 KB Output is correct
62 Correct 12 ms 3144 KB Output is correct
63 Correct 11 ms 3188 KB Output is correct
64 Correct 12 ms 3152 KB Output is correct
65 Correct 42 ms 3116 KB Output is correct
66 Partially correct 502 ms 3432 KB Partially correct - number of queries: 6029
67 Partially correct 478 ms 3420 KB Partially correct - number of queries: 5526
68 Partially correct 481 ms 3160 KB Partially correct - number of queries: 5774
69 Partially correct 532 ms 3476 KB Partially correct - number of queries: 6012
70 Correct 328 ms 3412 KB Output is correct
71 Partially correct 574 ms 3368 KB Partially correct - number of queries: 9516
72 Correct 45 ms 3348 KB Output is correct
73 Partially correct 541 ms 3472 KB Partially correct - number of queries: 9383
74 Partially correct 536 ms 3788 KB Partially correct - number of queries: 9440
75 Correct 11 ms 3188 KB Output is correct
76 Partially correct 431 ms 3468 KB Partially correct - number of queries: 8148
77 Partially correct 516 ms 3472 KB Partially correct - number of queries: 8822
78 Correct 55 ms 3340 KB Output is correct
79 Correct 248 ms 3440 KB Output is correct
80 Partially correct 568 ms 3456 KB Partially correct - number of queries: 8826
81 Partially correct 584 ms 3712 KB Partially correct - number of queries: 8870
82 Partially correct 589 ms 3740 KB Partially correct - number of queries: 8787
83 Correct 17 ms 3124 KB Output is correct
84 Partially correct 459 ms 3424 KB Partially correct - number of queries: 7329
85 Partially correct 569 ms 3476 KB Partially correct - number of queries: 8879
86 Partially correct 541 ms 3168 KB Partially correct - number of queries: 6033
87 Correct 57 ms 3096 KB Output is correct
88 Partially correct 527 ms 3068 KB Partially correct - number of queries: 5763
89 Partially correct 566 ms 3156 KB Partially correct - number of queries: 5993
90 Correct 12 ms 3072 KB Output is correct
91 Correct 320 ms 3540 KB Output is correct
92 Partially correct 598 ms 3484 KB Partially correct - number of queries: 5783
93 Partially correct 543 ms 3464 KB Partially correct - number of queries: 6203
94 Partially correct 564 ms 3468 KB Partially correct - number of queries: 6218
95 Partially correct 567 ms 3396 KB Partially correct - number of queries: 6208
96 Partially correct 532 ms 3244 KB Partially correct - number of queries: 6149
97 Partially correct 514 ms 3228 KB Partially correct - number of queries: 5780