oj.uz

답안 #1028739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028739 2024-07-20T07:54:57 Z parsadox2 커다란 상품 (IOI17_prize) C++17
20 / 100
 1000 ms 2088 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;
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -