#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
map<int, int> mp[213];
int ask(int i, int j)
{
if (i == j) return i;
if (mp[i].count(j))
{
return mp[i][j];
}
int res = CollectRelics(i, j);
mp[i][j] = res;
mp[j][i] = res;
// cerr << "ask " << i << ' ' << j << " = " << res << endl;
return res;
}
int FindBase(int N)
{
vi bucket, lis;
FOR(i, 0, N)
{
if (!lis.empty() && ask(lis.back(), i) != -1)
{
bucket.PB(i);
continue;
}
else
{
lis.PB(i);
if (!bucket.empty())
{
lis.PB(bucket.back());
bucket.pop_back();
}
}
}
int cand = lis.back();
// for (int x : lis)
// {
// cerr << x << ' ';
// }
// cerr << endl;
// cerr << "cand = " << bucket.back() << endl;
int maj = cand, num = 0;
while(!lis.empty())
{
int n = ask(cand, lis.back());
if (n == -1)
{
lis.pop_back();
if (bucket.empty())
{
break;
}
bucket.pop_back();
}
else
{
if (n == maj)
{
num++;
}
else
{
num--;
if (num == -1)
{
num = 1;
maj = n;
}
}
if (SZ(lis) == 1)
{
bucket.PB(lis.back());
lis.pop_back();
}
else
{
lis.pop_back();
int nn = ask(cand, lis.back());
if (nn == maj)
{
num++;
}
else
{
num--;
if (num == -1)
{
num = 1;
maj = nn;
}
}
lis.pop_back();
}
}
}
if (bucket.empty()) return -1;
for (int w : bucket)
{
int nn = ask(cand, w);
if (nn == maj)
{
num++;
}
else
{
num--;
if (num == -1)
{
num = 1;
maj = nn;
}
}
}
// cerr << "cand = " << cand << " maj = " << maj << endl;
return maj;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
6 ms |
640 KB |
Partially correct : C = 397 |
2 |
Partially correct |
5 ms |
640 KB |
Partially correct : C = 396 |
3 |
Partially correct |
5 ms |
768 KB |
Partially correct : C = 395 |
4 |
Partially correct |
5 ms |
640 KB |
Partially correct : C = 395 |
5 |
Correct |
5 ms |
640 KB |
Correct : C = 199 |
6 |
Correct |
5 ms |
640 KB |
Correct : C = 233 |
7 |
Correct |
5 ms |
640 KB |
Correct : C = 120 |
8 |
Correct |
5 ms |
512 KB |
Correct : C = 0 |
9 |
Partially correct |
6 ms |
640 KB |
Partially correct : C = 397 |
10 |
Correct |
5 ms |
640 KB |
Correct : C = 119 |
11 |
Correct |
5 ms |
640 KB |
Correct : C = 199 |
12 |
Partially correct |
5 ms |
640 KB |
Partially correct : C = 357 |
13 |
Correct |
5 ms |
640 KB |
Correct : C = 119 |
14 |
Correct |
5 ms |
512 KB |
Correct : C = 4 |
15 |
Correct |
5 ms |
640 KB |
Correct : C = 236 |
16 |
Correct |
5 ms |
640 KB |
Correct : C = 118 |
17 |
Partially correct |
5 ms |
640 KB |
Partially correct : C = 384 |
18 |
Correct |
5 ms |
640 KB |
Correct : C = 198 |
19 |
Correct |
5 ms |
640 KB |
Correct : C = 235 |
20 |
Correct |
5 ms |
640 KB |
Correct : C = 235 |
21 |
Correct |
5 ms |
640 KB |
Correct : C = 199 |
22 |
Partially correct |
5 ms |
640 KB |
Partially correct : C = 390 |
23 |
Correct |
5 ms |
640 KB |
Correct : C = 234 |
24 |
Partially correct |
5 ms |
768 KB |
Partially correct : C = 394 |
25 |
Correct |
5 ms |
640 KB |
Correct : C = 119 |
26 |
Correct |
5 ms |
640 KB |
Correct : C = 200 |
27 |
Correct |
5 ms |
640 KB |
Correct : C = 202 |