| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287466 | Kastanda | Scales (IOI15_scales) | C++11 | 309 ms | 235640 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
#include "scales.h"
#define pb push_back
using namespace std;
const int K = 6, MXN = 1e7, INF = 1e4;
int CalcHeaviest(vector < vector < int > > &, int, int, int, int, int);
int CalcLightest(vector < vector < int > > &, int, int, int, int, int);
int CalcMedian(vector < vector < int > > &, int, int, int, int, int);
int CalcNext(vector < vector < int > > &, int, int, int, int, int, int);
vector < vector < int > > DoHeaviest(vector < vector < int > > &now, int a, int b, int c, int t)
{
vector < vector < int > > tobe;
for (auto vec : now)
if (vec[a] <= vec[t] && vec[b] <= vec[t] && vec[c] <= vec[t])
tobe.pb(vec);
return tobe;
}
vector < vector < int > > DoLightest(vector < vector < int > > &now, int a, int b, int c, int t)
{
vector < vector < int > > tobe;
for (auto &vec : now)
if (vec[a] >= vec[t] && vec[b] >= vec[t] && vec[c] >= vec[t])
tobe.pb(vec);
return tobe;
}
vector < vector < int > > DoMedian(vector < vector < int > > &now, int a, int b, int c, int t)
{
if (a == t) a = c;
else if (b == t) b = c;
assert(a != t && b != t && a != b);
vector < vector < int > > tobe;
for (auto &vec : now)
if ((vec[a] < vec[t] && vec[b] > vec[t]) || (vec[a] > vec[t] && vec[b] < vec[t]))
tobe.pb(vec);
return tobe;
}
vector < vector < int > > DoNext(vector < vector < int > > &now, int a, int b, int c, int d, int t)
{
vector < vector < int > > tobe;
for (auto &vec : now)
{
vector < pair < int , int > > tmp;
tmp.pb({vec[a], a});
tmp.pb({vec[b], b});
tmp.pb({vec[c], c});
sort(tmp.begin(), tmp.end());
int lb = lower_bound(tmp.begin(), tmp.end(), make_pair(vec[d], d)) - tmp.begin();
if (lb == 3)
lb = 0;
if (tmp[lb].second == t)
tobe.pb(vec);
}
return tobe;
}
int ts, Rs[MXN];
vector < int > VM[MXN];
map < vector < vector < int > > , int > MP, PM[K + 1];
vector < vector < int > > All;
int DEF_TRN = 4;
int Solve(vector < vector < int > > now, int isFirstMove = 0, int TRN = DEF_TRN)
{
if (PM[TRN].count(now))
return Rs[PM[TRN][now]];
int atleast = 0, nwsz = (int)now.size();
while (nwsz > 1)
nwsz = (nwsz + 2) / 3, atleast ++;
if (atleast > TRN)
return INF;
int id = ++ ts;
PM[TRN][now] = id;
Rs[id] = INF;
if ((int)now.size() <= 1)
return Rs[id] = 0;
int MnMove = INF;
vector < int > VMove;
{
for (int a = 0; a < K; a ++)
for (int b = a + 1; b < K; b ++)
for (int c = b + 1; c < K; c ++)
{
if (MnMove < TRN)
continue;
for (int d = 0; d < K; d ++)
if (d != a && d != b && d != c)
{
int mx = CalcNext(now, a, b, c, d, a, TRN);
mx = max(mx, CalcNext(now, a, b, c, d, b, TRN));
mx = max(mx, CalcNext(now, a, b, c, d, c, TRN));
if (mx < MnMove)
{
MnMove = mx;
VMove = {3, a, b, c, d};
}
}
if (isFirstMove && (a != 0 || b != 1 || c != 2))
continue;
int mx = CalcHeaviest(now, a, b, c, a, TRN);
mx = max(mx, CalcHeaviest(now, a, b, c, b, TRN));
mx = max(mx, CalcHeaviest(now, a, b, c, c, TRN));
if (mx < MnMove)
{
MnMove = mx;
VMove = {0, a, b, c};
}
mx = CalcLightest(now, a, b, c, a, TRN);
mx = max(mx, CalcLightest(now, a, b, c, b, TRN));
mx = max(mx, CalcLightest(now, a, b, c, c, TRN));
if (mx < MnMove)
{
MnMove = mx;
VMove = {1, a, b, c};
}
mx = CalcMedian(now, a, b, c, a, TRN);
mx = max(mx, CalcMedian(now, a, b, c, b, TRN));
mx = max(mx, CalcMedian(now, a, b, c, c, TRN));
if (mx < MnMove)
{
MnMove = mx;
VMove = {2, a, b, c};
}
}
}
if (MnMove + 1 > TRN)
return INF;
Rs[id] = MnMove + 1;
VM[id] = VMove;
return Rs[id];
}
int CalcHeaviest(vector < vector < int > > &now, int a, int b, int c, int t, int TRN)
{
auto tobe = DoHeaviest(now, a, b, c, t);
if (tobe == now)
return INF;
return Solve(tobe, 0, TRN - 1);
}
int CalcLightest(vector < vector < int > > &now, int a, int b, int c, int t, int TRN)
{
auto tobe = DoLightest(now, a, b, c, t);
if (tobe == now)
return INF;
return Solve(tobe, 0, TRN - 1);
}
int CalcMedian(vector < vector < int > > &now, int a, int b, int c, int t, int TRN)
{
auto tobe = DoMedian(now, a, b, c, t);
if (tobe == now)
return INF;
return Solve(tobe, 0, TRN - 1);
}
int CalcNext(vector < vector < int > > &now, int a, int b, int c, int d, int t, int TRN)
{
auto tobe = DoNext(now, a, b, c, d, t);
if (tobe == now)
return INF;
return Solve(tobe, 0, TRN - 1);
}
void init(int T)
{
ts = 0;
All.clear();
vector < int > P(K);
iota(P.begin(), P.end(), 0);
do {
All.pb(P);
} while (next_permutation(P.begin(), P.end()));
All = DoLightest(All, 0, 1, 2, 2);
All = DoMedian(All, 3, 4, 5, 5);
assert(Solve(All, 1, 4) <= 4);
}
void orderCoins()
{
vector < int > P(K), Rev(K + 1);
for (int i = 0; i < K; i ++)
P[i] = i + 1;
vector < vector < int > > now = All;
{
int lt = getLightest(0 + 1, 1 + 1, 2 + 1) - 1;
swap(P[lt], P[2]);
int md = getMedian(3 + 1, 4 + 1, 5 + 1) - 1;
swap(P[md], P[5]);
}
for (int i = 0; i < K; i ++)
Rev[P[i]] = i;
int TRN = 4;
while (now.size() > 1)
{
assert(PM[TRN].count(now));
int id = PM[TRN][now];
TRN --;
vector < int > VMove = VM[id];
if (VMove[0] == 0)
{
int hv = Rev[getHeaviest(P[VMove[1]], P[VMove[2]], P[VMove[3]])];
now = DoHeaviest(now, VMove[1], VMove[2], VMove[3], hv);
continue;
}
else if (VMove[0] == 1)
{
int lt = Rev[getLightest(P[VMove[1]], P[VMove[2]], P[VMove[3]])];
now = DoLightest(now, VMove[1], VMove[2], VMove[3], lt);
continue;
}
else if (VMove[0] == 2)
{
int md = Rev[getMedian(P[VMove[1]], P[VMove[2]], P[VMove[3]])];
now = DoMedian(now, VMove[1], VMove[2], VMove[3], md);
continue;
}
else if (VMove[0] == 3)
{
int nx = Rev[getNextLightest(P[VMove[1]], P[VMove[2]], P[VMove[3]], P[VMove[4]])];
now = DoNext(now, VMove[1], VMove[2], VMove[3], VMove[4], nx);
continue;
}
assert(0);
}
int W[6];
assert((int)now.size() == 1);
vector < int > rs = now[0];
for (int i = 0; i < K; i ++)
W[rs[i]] = P[i];
answer(W);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||