| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 247320 | 2020-07-11T08:45:38 Z | dantoh000 | 로카히아 유적 (FXCUP4_lokahia) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
//#include "lokahia.h"
int Q[205][205];
int tq = 0;
int query(int i, int j){
if (i == j) return Q[i][i] = i;
else if (tq >= 400) return -1;
else if (Q[i][j] == -2) {
tq++;
return Q[i][j] = Q[j][i] = CollectRelics(i,j);
}
else return Q[i][j];
}
int FindBase(int N){
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) Q[i][j] = -2;
vector<int> good;
for (int i = 0; i < N; i++) good.push_back(i);
while (good.size() && tq <= 400){
int cur = good[0];
for (auto x : good){
if (cur == x) continue;
int q = query(cur,x);
if (q != -1 && q > cur) cur = q;
}
int ct = 0;
vector<int> bad;
for (auto x : good){
if (x == cur || query(x,cur) != -1) ct++;
else bad.push_back(x);
if (ct > N/2) break;
}
if (ct > N/2) return cur;
good.clear();
for (auto x : bad){
good.push_back(x);
}
bad.clear();
}
return -1;
}