oj.uz

Submission #150479

# Submission time Handle Problem Language Result Execution time Memory
150479 2019-09-01T08:29:38 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 9 ms 640 KB 
#include "lokahia.h"

#include <vector>
#include<stdio.h>
using namespace std;
using pii=pair<int,int>;
vector<vector<pii>> V;
vector<int> W;

int Query(int x,int y){
	//printf("%d %d\n",x,y);
	if(x==y)return x;
	else return CollectRelics(x,y);
}

int FindBase(int N){
	for(int i=0;i<N;){
		int j=i+1;
		int c1=1,c2=0,cur=i;
		vector<pii> T;
		T.emplace_back(i,1);
		while(j<N&&c1!=c2){
			int k=Query(cur,j);
			if(k==-1){
				c2++;
				T.emplace_back(j,0);
			}
			else{
				c1++;
				cur=k;
				T.emplace_back(j,1);
			}
			j++;
		}
		W.push_back(cur);
		V.push_back(T);
		i=j;
	}
	int sz=V.size();
	int cand=W.back();
	int num=0;
	for(auto &x:V.back())num+=x.second;
	for(int i=sz-1;i--;){
		int k=Query(cand,W[i]);
		if(k==-1){
			for(auto &x:V[i])if(x.second==0){
				k=Query(cand,x.first);
				if(k!=-1){
					num++;
					cand=k;
				}
			}
		}
		else{
			for(auto &x:V[i])num+=x.second;
			cand=k;
		}
	}
	if(num>N/2)return cand;
	else return -1;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Correct : C = 119
2 Correct 6 ms 512 KB Correct : C = 177
3 Correct 6 ms 640 KB Correct : C = 199
4 Correct 6 ms 640 KB Correct : C = 198
5 Correct 6 ms 640 KB Correct : C = 198
6 Correct 6 ms 512 KB Correct : C = 176
7 Correct 7 ms 640 KB Correct : C = 297
8 Correct 7 ms 640 KB Correct : C = 273
9 Correct 6 ms 512 KB Correct : C = 178
10 Correct 6 ms 640 KB Correct : C = 203
11 Correct 6 ms 640 KB Correct : C = 197
12 Correct 6 ms 512 KB Correct : C = 120
13 Correct 8 ms 512 KB Correct : C = 118
14 Correct 6 ms 512 KB Correct : C = 163
15 Correct 6 ms 512 KB Correct : C = 4
16 Correct 5 ms 640 KB Correct : C = 298
17 Correct 9 ms 640 KB Correct : C = 205
18 Correct 7 ms 640 KB Correct : C = 197
19 Correct 5 ms 512 KB Correct : C = 118
20 Correct 6 ms 512 KB Correct : C = 117
21 Correct 6 ms 640 KB Correct : C = 202
22 Correct 5 ms 512 KB Correct : C = 0
23 Correct 7 ms 640 KB Correct : C = 276
24 Correct 7 ms 640 KB Correct : C = 194
25 Correct 6 ms 640 KB Correct : C = 262
26 Correct 5 ms 512 KB Correct : C = 117
27 Correct 6 ms 636 KB Correct : C = 251