| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 379249 | 2021-03-17T15:21:57 Z | tqbfjotld | 로카히아 유적 (FXCUP4_lokahia) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
//#include "lokahia.h"
int X[205];
int retval[205];
int FindBase(int N){
if (N==1) return 0;
for (int x = 0; x<N; x++){
X[x] = x;
}
for (int x = 0; x<N-1; x++){
retval[x+1] = CollectRelics(x,x+1);
if (retval[x+1]!=-1){
X[x+1] = X[x];
}
}
int longest = -1;
int longpos = -1;
for (int x = 0; x<N; x++){
if (x-X[x]>longest){
longest = x-X[x];
longpos = x;
}
}
int fingroup = X[longpos];
int cur = N-1;
int compsize = longest+1;
int ans = -2;
for (int x = fingroup+1; X[x]==fingroup&&x<N; x++){
ans = max(ans,retval[x]);
}
int queryCount = N-1;
while (cur!=-1){
if (X[cur]!=0 && X[X[cur]-1]==fingroup){
cur = X[cur]-1;
continue;
}
if (X[cur]==fingroup){
cur = X[cur]-1;
continue;
}
if (cur+1==fingroup){
cur = X[cur]-1;
continue;
}
if (compsize>N/2) return ans;
if (queryCount==300) return -1;
int ret = CollectRelics(cur,fingroup);
queryCount++;
if (ret==-1){
cur = X[cur]-1;
continue;
}
else{
compsize += cur-X[cur]+1;
ans = max(ans,ret);
if (X[cur]==0) cur = -1;
else cur = X[X[cur]-1]-1;
}
}
if (compsize>N/2) assert(ans!=-2);
return compsize>N/2?ans:-1;
}