oj.uz

Submission #1028735

# Submission time Handle Problem Language Result Execution time Memory
1028735 2024-07-20T07:51:11 Z parsadox2 The Big Prize (IOI17_prize) C++17
20 / 100
 860 ms 2208 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

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

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

void Solve()
{
	vector <int> all;
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
		all.push_back(i);
	int m = all.size() , sq = Sq(m);
	if(m == 1)
		return;
	int mx = 0;
	for(int i = 0 ; i < sq ; i++)
	{
		auto now = ask(all[i]);
		mx = max(mx , now[0] + now[1]);
	}
	for(auto u : all)
		marked[u] = false;
	for(int asd = 0 ; asd < mx ; asd++)
	{
		all.clear();
		for(int i = 0 ; i < n ; i++)  if(!dead[i] && !marked[i])
			all.push_back(i);
		m = all.size();
		int low = -1 , high = m;
		while(high - low > 1)
		{
			int mid = (low + high) >> 1;
			int id = all[mid];
			auto now = ask(id);
			if(now[0] + now[1] != mx)
			{
				marked[id] = true;
				break;
			}
			dead[id] = true;
			for(int i = 0 ; i < id ; i++)  if(!dead[i] && marked[i])
				now[0]--;
			if(now[0] == 0)
				low = mid;
			else
				high = mid;
		}
	}
	for(int i = 0 ; i < n ; i++)  if(!marked[i])
		dead[i] = true;
	Solve();
}

int find_best(int nn) {
	n = nn;
	Solve();
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
		return i;
	return -1;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1740 KB Output is correct
2 Correct 5 ms 1740 KB Output is correct
3 Correct 5 ms 1740 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 6 ms 1740 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 7 ms 1628 KB Output is correct
8 Correct 5 ms 1740 KB Output is correct
9 Correct 4 ms 1736 KB Output is correct
10 Correct 6 ms 1992 KB Output is correct
11 Correct 57 ms 1676 KB Output is correct
12 Correct 53 ms 1728 KB Output is correct
13 Correct 59 ms 1692 KB Output is correct
14 Correct 31 ms 600 KB Output is correct
15 Partially correct 732 ms 1732 KB Partially correct - number of queries: 7863
16 Partially correct 779 ms 1740 KB Partially correct - number of queries: 8531
17 Partially correct 758 ms 1748 KB Partially correct - number of queries: 8605
18 Partially correct 714 ms 1648 KB Partially correct - number of queries: 8503
19 Partially correct 657 ms 1676 KB Partially correct - number of queries: 7986
20 Partially correct 298 ms 1336 KB Partially correct - number of queries: 5592
21 Partially correct 731 ms 1864 KB Partially correct - number of queries: 8402
22 Partially correct 480 ms 1828 KB Partially correct - number of queries: 6244
23 Correct 14 ms 1740 KB Output is correct
24 Correct 43 ms 1488 KB Output is correct
25 Partially correct 701 ms 2092 KB Partially correct - number of queries: 8385
26 Partially correct 728 ms 1952 KB Partially correct - number of queries: 8514
27 Correct 13 ms 1740 KB Output is correct
28 Partially correct 771 ms 2088 KB Partially correct - number of queries: 8382
29 Partially correct 650 ms 1992 KB Partially correct - number of queries: 6944
30 Partially correct 860 ms 1720 KB Partially correct - number of queries: 8391
31 Partially correct 783 ms 2192 KB Partially correct - number of queries: 8367
32 Correct 58 ms 1488 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 802 ms 1780 KB Partially correct - number of queries: 8406
35 Correct 22 ms 1624 KB Output is correct
36 Partially correct 671 ms 1740 KB Partially correct - number of queries: 8390
37 Correct 56 ms 1632 KB Output is correct
38 Correct 23 ms 1624 KB Output is correct
39 Partially correct 763 ms 1932 KB Partially correct - number of queries: 8354
40 Partially correct 617 ms 1920 KB Partially correct - number of queries: 7160
41 Partially correct 763 ms 1732 KB Partially correct - number of queries: 8517
42 Partially correct 824 ms 1720 KB Partially correct - number of queries: 8517
43 Partially correct 808 ms 2208 KB Partially correct - number of queries: 8195
44 Partially correct 826 ms 1912 KB Partially correct - number of queries: 8486
45 Partially correct 724 ms 1696 KB Partially correct - number of queries: 8417
46 Partially correct 841 ms 1896 KB Partially correct - number of queries: 8444
47 Partially correct 672 ms 1868 KB Partially correct - number of queries: 8390
48 Partially correct 759 ms 1940 KB Partially correct - number of queries: 8550
49 Partially correct 803 ms 2168 KB Partially correct - number of queries: 8439
50 Partially correct 752 ms 1488 KB Partially correct - number of queries: 8502
51 Partially correct 821 ms 1888 KB Partially correct - number of queries: 8489
52 Partially correct 778 ms 1992 KB Partially correct - number of queries: 8436
53 Correct 25 ms 1624 KB Output is correct
54 Partially correct 768 ms 1728 KB Partially correct - number of queries: 8463
55 Partially correct 813 ms 1988 KB Partially correct - number of queries: 8502
56 Partially correct 808 ms 1736 KB Partially correct - number of queries: 8515
57 Partially correct 732 ms 1872 KB Partially correct - number of queries: 8421
58 Partially correct 788 ms 2120 KB Partially correct - number of queries: 8505
59 Partially correct 756 ms 1824 KB Partially correct - number of queries: 8516
60 Partially correct 745 ms 1584 KB Partially correct - number of queries: 8420
61 Correct 14 ms 1740 KB Output is correct
62 Correct 15 ms 1740 KB Output is correct
63 Correct 14 ms 1740 KB Output is correct
64 Correct 18 ms 1644 KB Output is correct
65 Correct 30 ms 1488 KB Output is correct
66 Partially correct 710 ms 1576 KB Partially correct - number of queries: 5661
67 Incorrect 602 ms 1568 KB answer is not correct
68 Halted 0 ms 0 KB -