// 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
scales.cpp: In function 'std::vector<std::vector<int> > DoNext(std::vector<std::vector<int> >&, int, int, int, int, int)':
scales.cpp:50:84: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
50 | int lb = lower_bound(tmp.begin(), tmp.end(), make_pair(vec[d], d)) - tmp.begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:171:15: warning: unused parameter 'T' [-Wunused-parameter]
171 | void init(int T)
| ~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
210 ms |
235568 KB |
Output is correct |
| 2 |
Correct |
217 ms |
235512 KB |
Output is correct |
| 3 |
Correct |
220 ms |
235544 KB |
Output is correct |
| 4 |
Correct |
221 ms |
235588 KB |
Output is correct |
| 5 |
Correct |
212 ms |
235616 KB |
Output is correct |
| 6 |
Correct |
213 ms |
235512 KB |
Output is correct |
| 7 |
Correct |
229 ms |
235512 KB |
Output is correct |
| 8 |
Correct |
213 ms |
235512 KB |
Output is correct |
| 9 |
Correct |
206 ms |
235524 KB |
Output is correct |
| 10 |
Correct |
216 ms |
235516 KB |
Output is correct |
| 11 |
Correct |
209 ms |
235512 KB |
Output is correct |
| 12 |
Correct |
238 ms |
235528 KB |
Output is correct |
| 13 |
Correct |
223 ms |
235524 KB |
Output is correct |
| 14 |
Correct |
232 ms |
235512 KB |
Output is correct |
| 15 |
Correct |
225 ms |
235564 KB |
Output is correct |
| 16 |
Correct |
210 ms |
235512 KB |
Output is correct |
| 17 |
Correct |
210 ms |
235512 KB |
Output is correct |
| 18 |
Correct |
225 ms |
235540 KB |
Output is correct |
| 19 |
Correct |
257 ms |
235584 KB |
Output is correct |
| 20 |
Correct |
228 ms |
235536 KB |
Output is correct |
| 21 |
Correct |
210 ms |
235588 KB |
Output is correct |
| 22 |
Correct |
210 ms |
235604 KB |
Output is correct |
| 23 |
Correct |
224 ms |
235496 KB |
Output is correct |
| 24 |
Correct |
218 ms |
235584 KB |
Output is correct |
| 25 |
Correct |
207 ms |
235512 KB |
Output is correct |
| 26 |
Correct |
229 ms |
235540 KB |
Output is correct |
| 27 |
Correct |
254 ms |
235608 KB |
Output is correct |
| 28 |
Correct |
216 ms |
235544 KB |
Output is correct |
| 29 |
Correct |
212 ms |
235512 KB |
Output is correct |
| 30 |
Correct |
218 ms |
235532 KB |
Output is correct |
| 31 |
Correct |
197 ms |
235512 KB |
Output is correct |
| 32 |
Correct |
269 ms |
235536 KB |
Output is correct |
| 33 |
Correct |
309 ms |
235512 KB |
Output is correct |
| 34 |
Correct |
199 ms |
235512 KB |
Output is correct |
| 35 |
Correct |
215 ms |
235512 KB |
Output is correct |
| 36 |
Correct |
205 ms |
235512 KB |
Output is correct |
| 37 |
Correct |
221 ms |
235512 KB |
Output is correct |
| 38 |
Correct |
228 ms |
235640 KB |
Output is correct |
| 39 |
Correct |
208 ms |
235512 KB |
Output is correct |
| 40 |
Correct |
210 ms |
235640 KB |
Output is correct |
