| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287345 | Kastanda | Scales (IOI15_scales) | C++11 | 239 ms | 235772 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 > > &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 ((int)tobe.size());
}
int CalcLightest(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 ((int)tobe.size());
}
int CalcMedian(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 ((int)tobe.size());
}
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;
}
int ts, Rs[MXN];
vector < int > VM[MXN];
map < vector < vector < int > > , int > MP;
vector < vector < int > > All;
int Solve(vector < vector < int > > now, int isFirstMove = 0)
{
if (MP.count(now))
return Rs[MP[now]];
int id = ++ ts;
MP[now] = id;
Rs[id] = INF;
if ((int)now.size() <= 1)
{
Rs[id] = 0;
return 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 (isFirstMove && (a != 0 || b != 1 || c != 2))
continue;
int mx = CalcHeaviest(now, a, b, c, a);
mx = max(mx, CalcHeaviest(now, a, b, c, b));
mx = max(mx, CalcHeaviest(now, a, b, c, c));
if (mx < MnMove)
{
MnMove = mx;
VMove = {0, a, b, c};
}
}
}
{
for (int a = 0; a < K; a ++)
for (int b = a + 1; b < K; b ++)
for (int c = b + 1; c < K; c ++)
{
if (isFirstMove && (a != 0 || b != 1 || c != 2))
continue;
int mx = CalcLightest(now, a, b, c, a);
mx = max(mx, CalcLightest(now, a, b, c, b));
mx = max(mx, CalcLightest(now, a, b, c, c));
if (mx < MnMove)
{
MnMove = mx;
VMove = {1, a, b, c};
}
}
}
{
for (int a = 0; a < K; a ++)
for (int b = a + 1; b < K; b ++)
for (int c = b + 1; c < K; c ++)
{
if (isFirstMove && (a != 0 || b != 1 || c != 2))
continue;
int mx = CalcMedian(now, a, b, c, a);
mx = max(mx, CalcMedian(now, a, b, c, b));
mx = max(mx, CalcMedian(now, a, b, c, c));
if (mx < MnMove)
{
MnMove = mx;
VMove = {2, a, b, c};
}
}
}
Rs[id] = 0;
if (VMove[0] == 0)
{
for (int i = 1; i <= 3; i ++)
Rs[id] = max(Rs[id], Solve(DoHeaviest(now, VMove[1], VMove[2], VMove[3], VMove[i])));
}
if (VMove[0] == 1)
{
for (int i = 1; i <= 3; i ++)
Rs[id] = max(Rs[id], Solve(DoLightest(now, VMove[1], VMove[2], VMove[3], VMove[i])));
}
if (VMove[0] == 2)
{
for (int i = 1; i <= 3; i ++)
Rs[id] = max(Rs[id], Solve(DoMedian(now, VMove[1], VMove[2], VMove[3], VMove[i])));
}
Rs[id] ++;
VM[id] = VMove;
return Rs[id];
}
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()));
cerr << Solve(All, 1) << endl;
}
void orderCoins()
{
vector < vector < int > > now = All;
int cnt = 0;
while (now.size() > 1)
{
cnt ++;
assert(cnt <= 7);
assert(MP.count(now));
int id = MP[now];
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;
}
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... | ||||