Submission #147842

#	Time	Username	Problem	Language	Result	Execution time	Memory
147842		imsifile	Lokahian Relics (FXCUP4_lokahia)	C++17	100 / 100	8 ms	976 KiB

lokahia

#include "lokahia.h"
#include <vector>
using namespace std;

vector<int> my[202], adv[202];
int gcn, res[202][202], cnts[202];

int comp(int x, int y){
	if(res[x][y]==-2) return res[x][y]=res[y][x]=CollectRelics(x,y);
	return res[x][y];
}

int FindBase(int N){
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++) res[i][j]=-2;
	}
	my[gcn].push_back(0);
	for(int i=1; i<N; i++){
		int d = comp(my[gcn][0], i);
		if(d<0) adv[gcn].push_back(i);
		else my[gcn].push_back(i);
		if(my[gcn].size() == adv[gcn].size()){
			i++, gcn++;
			if(i==N) return -1;
			my[gcn].push_back(i);
		}
	}
	int myt=my[gcn].size();
	for(int i=0; i<gcn; i++){
		if(comp(my[i][0], my[gcn][0]) < 0){
			for(auto &x: adv[i]){
				int d = comp(x, my[gcn][0]);
				if(d>=0) myt++, cnts[d]++;
			}
		}
		else{
			for(auto &x: my[i]){
				int d = comp(x, my[gcn][0]);
				if(d>=0) myt++, cnts[d]++;
			}
		}
	}
	for(auto &x: my[gcn]){
		if(x==my[gcn][0]) continue;
		cnts[comp(x, my[gcn][0])]++;
	}
	if(myt <= N/2) return -1;

	int mx=-1, mxi=0;
	for(int i=0; i<N; i++){
		if(cnts[i]>mx) mx=cnts[i], mxi=i;
	}
	return mxi;
}

• Subtask 1: 100 / 100