| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1271433 | Faggi | Scales (IOI15_scales) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
void answer(int C[]);
void init(int T)
{
}
bool cond(ll p[], ll d, ll k)
{
if (d == 0 && p[k] < p[(k + 1) % 3] && p[k] < p[(k + 2) % 3])
return 1;
if (d == 1 && ((p[k] > p[(k + 1) % 3] && p[k] < p[(k + 2) % 3]) || (p[k] < p[(k + 1) % 3] && p[k] > p[(k + 2) % 3])))
return 1;
if (d == 2 && p[k] > p[(k + 1) % 3] && p[k] > p[(k + 2) % 3])
return 1;
return 0;
}
vector<vector<ll>> all, all2;
ll calcLMH(ll a, ll b, ll c, ll d)
{
ll i, p[3], j, A[3] = {0, 0, 0}, k, ma, l;
for (l = 0; l < 3; l++)
{
for (k = 0; k < 3; k++)
{
for (i = 0; i < sz(all); i++)
{
for (j = 0; j < sz(all[i]); j++)
{
if (a == all[i][j])
p[0] = j;
if (b == all[i][j])
p[1] = j;
if (c == all[i][j])
p[2] = j;
}
if (cond(p, d, k))
A[k]++;
}
}
}
for(i=0; i<3; i++)
if(A[i]==0)
A[i]=INT_MAX;
ma = max(A[0], max(A[1], A[2]));
if (ma == 0)
return INT_MAX;
ll ret=min(A[0],min(A[1],A[2]));
return ret;
}
ll calcNL(ll a, ll b, ll c, ll d, ll ak, vector<vector<ll>>&all2)
{
ll i, p[4], A[3] = {0, 0, 0}, k, ma, j, m, vals[3];
vals[0]=a;
vals[1]=b;
vals[2]=c;
for (k = 0; k < 3; k++)
{
for (i = 0; i < sz(all); i++)
{
if(all[i][0]==4&&all[i][1]==2)
{
j=0;
}
for (j = 0; j < sz(all[i]); j++)
{
if (all[i][j] == a)
p[0] = j;
else if (all[i][j] == b)
p[1] = j;
else if (all[i][j] == c)
p[2] = j;
else if (all[i][j] == d)
p[3] = j;
}
vector<ll> ps = {p[0], p[1], p[2]};
sort(all(ps));
if (ps.back() > p[3])
{
ll v;
for (v = 0; v < 3; v++)
if (ps[v] > p[3])
{
break;
}
if (ps[v] == p[k])
{
A[k]++;
if(ak==vals[k])
all2.pb(all[i]);
}
}
else if (ps[0] == p[k])
{
A[k]++;
if(ak==vals[k])
all2.pb(all[i]);
}
}
}
for(i=0; i<3; i++)
if(A[i]==0)
A[i]=INT_MAX;
ll ret=min(A[0],min(A[1],A[2]));
return ret;
}
void orderCoins()
{
all.resize(0);
vector<ll> v = {1, 2, 3, 4, 5, 6};
do
{
all.pb(v);
} while (next_permutation(all(v)));
while (sz(all) > 1)
{
ll mi = LLONG_MAX, t = 0, i, j, k, c, l, tam = sz(all);
vector<ll> v = {1, 2, 3};
for (l = 0; l < 3; l++)
{
for (i = 1; i <= 6; i++)
{
for (j = i + 1; j <= 6; j++)
{
for (k = j + 1; k <= 6; k++)
{
c = calcLMH(i, j, k, l);
if (c < mi)
{
mi = c;
t = l;
v = {i, j, k};
}
}
}
}
}
for (i = 1; i <= 6; i++)
{
for (j = i + 1; j <= 6; j++)
{
for (k = j + 1; k <= 6; k++)
{
for (l = 1; l <= 6; l++)
{
if (l == i || l == j || l == k)
continue;
c = calcNL(i, j, k, l, -1, all2);
if (c < mi)
{
mi = c;
t = 3;
v = {i, j, k, l};
}
}
}
}
}
// Consulta
switch (t)
{
case 0:
c = getLightest(v[0], v[1], v[2]);
break;
case 1:
c = getMedian(v[0], v[1], v[2]);
break;
case 2:
c = getHeaviest(v[0], v[1], v[2]);
break;
default:
c = getNextLightest(v[0], v[1], v[2], v[3]);
break;
}
if (t < 3)
{
ll p[3], pos;
for (k = 0; k < 3; k++)
if (v[k] == c)
pos = k;
for (i = 0; i < sz(all); i++)
{
for (j = 0; j < sz(all[i]); j++)
{
for (k = 0; k < 3; k++)
{
if (v[k] == all[i][j])
p[k] = j;
}
}
if (cond(p, t, pos))
all2.pb(all[i]);
}
}
else
{
calcNL(v[0],v[1],v[2],v[3],c,all2);
}
swap(all, all2);
all2.resize(0);
}
int C[6];
for (ll i = 0; i < 6; i++)
C[i] = all[0][i];
answer(C);
}