oj.uz

Submission #147842

# Submission time Handle Problem Language Result Execution time Memory
147842 2019-08-31T00:09:41 Z imsifile Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 8 ms 976 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 768 KB Correct : C = 289
2 Correct 7 ms 768 KB Correct : C = 199
3 Correct 6 ms 768 KB Correct : C = 215
4 Correct 6 ms 512 KB Correct : C = 0
5 Correct 6 ms 692 KB Correct : C = 177
6 Correct 7 ms 896 KB Correct : C = 287
7 Correct 6 ms 640 KB Correct : C = 60
8 Correct 6 ms 860 KB Correct : C = 100
9 Correct 7 ms 640 KB Correct : C = 122
10 Correct 6 ms 640 KB Correct : C = 169
11 Correct 6 ms 640 KB Correct : C = 169
12 Correct 6 ms 640 KB Correct : C = 119
13 Correct 7 ms 768 KB Correct : C = 204
14 Correct 7 ms 640 KB Correct : C = 128
15 Correct 6 ms 768 KB Correct : C = 198
16 Correct 8 ms 976 KB Correct : C = 191
17 Correct 7 ms 640 KB Correct : C = 118
18 Correct 7 ms 856 KB Correct : C = 199
19 Correct 6 ms 640 KB Correct : C = 150
20 Correct 7 ms 768 KB Correct : C = 290
21 Correct 7 ms 768 KB Correct : C = 276
22 Correct 7 ms 768 KB Correct : C = 297
23 Correct 7 ms 768 KB Correct : C = 198
24 Correct 6 ms 768 KB Correct : C = 291
25 Correct 5 ms 512 KB Correct : C = 4
26 Correct 7 ms 768 KB Correct : C = 111
27 Correct 6 ms 640 KB Correct : C = 177