| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287433 | Kastanda | Scales (IOI15_scales) | C++11 | 1116 ms | 236572 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()));
}
void orderCoins()
{
for (int i = 0; i <= K; i ++)
PM[i].clear();
ts = 0;
vector < vector < int > > now = All;
{
int lt = getLightest(0 + 1, 1 + 1, 2 + 1) - 1;
now = DoLightest(now, 0, 1, 2, lt);
int md = getMedian(3 + 1, 4 + 1, 5 + 1) - 1;
now = DoMedian(now, 3, 4, 5, md);
cerr << Solve(now, 1, 4) << endl;
}
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 = getHeaviest(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1) - 1;
now = DoHeaviest(now, VMove[1], VMove[2], VMove[3], hv);
continue;
}
else if (VMove[0] == 1)
{
int lt = getLightest(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1) - 1;
now = DoLightest(now, VMove[1], VMove[2], VMove[3], lt);
continue;
}
else if (VMove[0] == 2)
{
int md = getMedian(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1) - 1;
now = DoMedian(now, VMove[1], VMove[2], VMove[3], md);
continue;
}
else if (VMove[0] == 3)
{
int nx = getNextLightest(VMove[1] + 1, VMove[2] + 1, VMove[3] + 1, VMove[4] + 1) - 1;
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]] = i + 1;
answer(W);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||