Submission #150479

#	Time	Username	Problem	Language	Result	Execution time	Memory
150479		강력한 한방 필살기 (#200)	Lokahian Relics (FXCUP4_lokahia)	C++17	100 / 100	9 ms	640 KiB

lokahia

#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 / 100