oj.uz

Submission #151455

# Submission time Handle Problem Language Result Execution time Memory
151455 2019-09-03T09:11:59 Z babo Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 1000 ms 636 KB 
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

int CollectRelics(int,int);

multiset<pair<int,int> >st,st2,st3;

int FindBase(int N){
	int i;
	for(i=0;i<N;i++)
	{
		st.insert(make_pair(1,i));
	}
	while(st.size()>=2)
	{
		//printf("sz %d , %d %d %d %d %d\n",st.size(),st.begin()->y,next(st.begin())->y,st.begin()->x,next(st.begin())->x);
		//printf(" %d\n",CollectRelics(st.begin()->y,next(st.begin())->y));
		if(st.begin()->x==next(st.begin())->x)
		{
			int temp=st.begin()->y==next(st.begin())->y?st.begin()->y:CollectRelics(st.begin()->y,next(st.begin())->y);
			if(temp!=-1)
			{
				//printf("%d\n",st.size());
				st.erase(next(st.begin()));
				st.insert(make_pair(st.begin()->x*2,temp));
				st.erase(st.begin());	
				//printf("%d\n",st.size());
			}
			else
			{
				st2.insert(*st.begin());
				st.erase(st.begin());
				st2.insert(*st.begin());
				st.erase(st.begin());
			}
		}
		else
		{
			st3.insert(*st.begin());
			st.erase(st.begin());
		}
	}
	int las,ans;
	if(st.empty())
	{
		if(st3.empty())
			return -1;
		else
		{
			las=st3.rbegin()->y;
			ans=st3.rbegin()->x;
		}
	}
	else
	{
		las=st.begin()->y;
		ans=st.begin()->x;
	}
	st.erase(st.begin());
	for(multiset<pair<int,int> >::iterator it=st2.begin();it!=st2.end();it++)
	{
		int temp=las==it->y?las:CollectRelics(las,it->y);
		if(temp!=-1)
		{
			las=temp;
			ans+=it->x;
		}
	}
	if(ans>N/2)
		return las;
	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 636 KB Wrong
2 Correct 2 ms 504 KB Correct : C = 59
3 Correct 3 ms 632 KB Correct : C = 229
4 Correct 3 ms 632 KB Correct : C = 102
5 Correct 2 ms 424 KB Correct : C = 2
6 Correct 2 ms 632 KB Correct : C = 250
7 Correct 2 ms 548 KB Correct : C = 297
8 Correct 2 ms 632 KB Correct : C = 230
9 Correct 2 ms 504 KB Correct : C = 147
10 Incorrect 2 ms 632 KB Wrong
11 Correct 3 ms 632 KB Correct : C = 100
12 Correct 3 ms 628 KB Correct : C = 99
13 Execution timed out 3011 ms 504 KB Time limit exceeded
14 Correct 3 ms 632 KB Correct : C = 240
15 Correct 2 ms 632 KB Correct : C = 60
16 Execution timed out 3083 ms 504 KB Time limit exceeded
17 Correct 2 ms 504 KB Correct : C = 146
18 Correct 2 ms 632 KB Correct : C = 100
19 Correct 3 ms 632 KB Correct : C = 104
20 Correct 2 ms 504 KB Correct : C = 177
21 Correct 2 ms 376 KB Correct : C = 0
22 Correct 3 ms 632 KB Correct : C = 200
23 Incorrect 3 ms 632 KB Wrong
24 Execution timed out 3044 ms 632 KB Time limit exceeded
25 Correct 2 ms 632 KB Correct : C = 149
26 Incorrect 2 ms 504 KB Wrong
27 Correct 2 ms 504 KB Correct : C = 60