| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1284595 | kustov_vadim_533 | Scales (IOI15_scales) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <array>
#include <map>
#include <random>
#include <bitset>
#include <stack>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
//#include "scales.h"
using namespace std;
typedef long long ll;
const int N = 6;
const int F = 720;
int p[F][N], q[F][N];
struct op {
int a = 0, b = 0, c = 0, d = 0, t = -1;
bitset<F> m[3];
};
vector<op> ops;
void init(int T) {
vector<int> pr = { 0, 1, 2, 3, 4, 5 };
for (int i = 0; i < F; ++i) {
for (int j = 0; j < N; ++j) {
p[i][j] = pr[j];
q[i][p[i][j]] = j;
}
next_permutation(pr.begin(), pr.end());
}
op x;
for (x.a = 0; x.a < N; ++x.a) {
for (x.b = x.a + 1; x.b < N; ++x.b) {
for (x.c = x.b + 1; x.c < N; ++x.c) {
vector<int> v = { x.a, x.b, x.c };
x.t = 0;
for (int r = 0; r < 3; ++r) {
for (int i = 0; i < F; ++i) {
x.m[r][i] = (q[i][v[r]] >= q[i][x.a] && q[i][v[r]] >= q[i][x.b] && q[i][v[r]] >= q[i][x.c]);
}
}
ops.push_back(x);
x.t = 1;
for (int r = 0; r < 3; ++r) {
for (int i = 0; i < F; ++i) {
x.m[r][i] = (q[i][v[r]] <= q[i][x.a] && q[i][v[r]] <= q[i][x.b] && q[i][v[r]] <= q[i][x.c]);
}
}
ops.push_back(x);
x.t = 2;
for (int r = 0; r < 3; ++r) {
for (int i = 0; i < F; ++i) {
x.m[r][i] = !(q[i][v[r]] >= q[i][x.a] && q[i][v[r]] >= q[i][x.b] && q[i][v[r]] >= q[i][x.c]) && !(q[i][v[r]] <= q[i][x.a] && q[i][v[r]] <= q[i][x.b] && q[i][v[r]] <= q[i][x.c]);
}
}
ops.push_back(x);
for (x.d = x.c + 1; x.d < N; ++x.d) {
}
}
}
}
}
void orderCoins() {
bitset<F> cur;
for (int i = 0; i < F; ++i) {
cur[i] = true;
}
while (cur.count() > 1) {
int bs = 0;
int rs = cur.count();
for (int i = 0; i < ops.size(); ++i) {
int res = 0;
for (int j = 0; j < 3; ++j) {
res = max(res, (int)(cur & ops[i].m[j]).count());
}
if (res < rs) {
rs = res;
bs = i;
}
}
op ch = ops[bs];
if (ch.t == 0) {
int r = getHeaviest(ch.a + 1, ch.b + 1, ch.c + 1) - 1;
if (r == ch.a) r = 0;
else if (r == ch.b) r = 1;
else r = 2;
cur &= ch.m[r];
}
else if (ch.t == 1) {
int r = getLightest(ch.a + 1, ch.b + 1, ch.c + 1) - 1;
if (r == ch.a) r = 0;
else if (r == ch.b) r = 1;
else r = 2;
cur &= ch.m[r];
}
else if (ch.t == 2) {
int r = getMedian(ch.a + 1, ch.b + 1, ch.c + 1) - 1;
if (r == ch.a) r = 0;
else if (r == ch.b) r = 1;
else r = 2;
cur &= ch.m[r];
}
}
int ans[N];
for (int i = 0; i < F; ++i) {
if (cur[i]) {
for (int j = 0; j < N; ++j) {
ans[j] = p[i][j] + 1;
}
}
}
answer(ans);
}