Submission #1028739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028739	2024-07-20T07:54:57 Z	parsadox2	The Big Prize (IOI17_prize)	C++17	20 / 100	1000 ms	2088 KB

prize

#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;
	if(m < 500)
	{
		for(auto u : all)
		{
			auto now = ask(u);
			if(now[0] + now[1] != 0)
				dead[u] = true;
		}
		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	6 ms	1628 KB	Output is correct
3	Correct	6 ms	1740 KB	Output is correct
4	Correct	6 ms	1740 KB	Output is correct
5	Correct	5 ms	1740 KB	Output is correct
6	Correct	3 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	3 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	4 ms	1740 KB	Output is correct
6	Correct	4 ms	1740 KB	Output is correct
7	Correct	5 ms	1740 KB	Output is correct
8	Correct	7 ms	1740 KB	Output is correct
9	Correct	4 ms	1740 KB	Output is correct
10	Correct	7 ms	1740 KB	Output is correct
11	Correct	62 ms	1488 KB	Output is correct
12	Correct	91 ms	1676 KB	Output is correct
13	Correct	68 ms	1488 KB	Output is correct
14	Correct	39 ms	888 KB	Output is correct
15	Partially correct	880 ms	1968 KB	Partially correct - number of queries: 8281
16	Partially correct	993 ms	1584 KB	Partially correct - number of queries: 8774
17	Partially correct	891 ms	1988 KB	Partially correct - number of queries: 8835
18	Partially correct	941 ms	1820 KB	Partially correct - number of queries: 8748
19	Partially correct	969 ms	1836 KB	Partially correct - number of queries: 8258
20	Partially correct	332 ms	1244 KB	Partially correct - number of queries: 5731
21	Partially correct	919 ms	1896 KB	Partially correct - number of queries: 8674
22	Partially correct	648 ms	1676 KB	Partially correct - number of queries: 6517
23	Correct	16 ms	1740 KB	Output is correct
24	Correct	66 ms	1664 KB	Output is correct
25	Partially correct	893 ms	1824 KB	Partially correct - number of queries: 8645
26	Partially correct	993 ms	1488 KB	Partially correct - number of queries: 8758
27	Correct	13 ms	1740 KB	Output is correct
28	Partially correct	960 ms	2088 KB	Partially correct - number of queries: 8651
29	Partially correct	758 ms	1732 KB	Partially correct - number of queries: 7114
30	Partially correct	918 ms	1876 KB	Partially correct - number of queries: 8652
31	Partially correct	892 ms	1968 KB	Partially correct - number of queries: 8629
32	Correct	61 ms	1488 KB	Output is correct
33	Correct	1 ms	344 KB	Output is correct
34	Partially correct	926 ms	1928 KB	Partially correct - number of queries: 8668
35	Correct	29 ms	1488 KB	Output is correct
36	Partially correct	916 ms	1840 KB	Partially correct - number of queries: 8654
37	Correct	65 ms	2012 KB	Output is correct
38	Correct	16 ms	1620 KB	Output is correct
39	Partially correct	936 ms	1956 KB	Partially correct - number of queries: 8659
40	Partially correct	828 ms	1836 KB	Partially correct - number of queries: 7456
41	Partially correct	989 ms	1632 KB	Partially correct - number of queries: 8742
42	Execution timed out	1057 ms	2088 KB	Time limit exceeded
43	Halted	0 ms	0 KB	-