# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
831885 |
2023-08-20T16:49:49 Z |
Asymmetry |
Scales (IOI15_scales) |
C++17 |
|
300 ms |
612 KB |
#ifndef LOCAL
#include "scales.h"
#endif
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
// przyjmują wartościowanie
int applyLightest(vector<int> cur, int a, int b, int c) {
vector<int> xd = {a, b, c};
sort(xd.begin(), xd.end(), [&](int x, int y) {
return cur[x] < cur[y];
});
return xd[0];
}
int applyMedian(vector<int> cur, int a, int b, int c) {
vector<int> xd = {a, b, c};
sort(xd.begin(), xd.end(), [&](int x, int y) {
return cur[x] < cur[y];
});
return xd[1];
}
int applyHeaviest(vector<int> cur, int a, int b, int c) {
vector<int> xd = {a, b, c};
sort(xd.begin(), xd.end(), [&](int x, int y) {
return cur[x] < cur[y];
});
return xd[2];
}
int applyNextLightest(vector<int> cur, int a, int b, int c, int d) {
vector<int> xd = {a, b, c, d};
sort(xd.begin(), xd.end(), [&](int x, int y) {
return cur[x] < cur[y];
});
xd.emplace_back(xd[0]);
REP (i, ssize(xd) - 1)
if (xd[i] == d)
return xd[i + 1];
assert(false);
return -1;
}
#ifdef LOCAL
int query_cnt;
vector<int> per;
int getLightest(int a, int b, int c) {
++query_cnt;
return applyLightest(per, a - 1, b - 1, c - 1) + 1;
}
int getMedian(int a, int b, int c) {
++query_cnt;
return applyMedian(per, a - 1, b - 1, c - 1) + 1;
}
int getHeaviest(int a, int b, int c) {
++query_cnt;
return applyHeaviest(per, a - 1, b - 1, c - 1) + 1;
}
int getNextLightest(int a, int b, int c, int d) {
++query_cnt;
return applyNextLightest(per, a - 1, b - 1, c - 1, d - 1) + 1;
}
void answer(int t[6]) {
REP (i, 6)
debug(i, t[i]);
REP (i, 6)
assert(1 <= t[i] && t[i] <= 6);
REP (i, 5)
assert(per[t[i] - 1] < per[t[i + 1] - 1]);
}
#endif
const int N = 6;
void init(int tests) {
assert(tests);
}
void orderCoins() {
mt19937 rng(12938721);
auto rd = [&](int l, int r) {
return int(rng() % (r - l + 1) + l);
};
auto apply_move = [&](vector<vector<int>> perms, tuple<int, int, int, int, int> move) {
auto [type, a, b, c, d] = move;
map<int, vector<vector<int>>> mp;
for (auto v : perms) {
if (type == 0)
mp[applyLightest(v, a, b, c)].emplace_back(v);
else if (type == 1)
mp[applyMedian(v, a, b, c)].emplace_back(v);
else if (type == 2)
mp[applyHeaviest(v, a, b, c)].emplace_back(v);
else
mp[applyNextLightest(v, a, b, c, d)].emplace_back(v);
}
return tuple(mp[a], mp[b], mp[c]);
};
vector<vector<int>> cur_perms;
vector<int> cur(N);
iota(cur.begin(), cur.end(), 0);
do {
cur_perms.emplace_back(cur);
} while (next_permutation(cur.begin(), cur.end()));
while (ssize(cur_perms) > 1) {
debug(ssize(cur_perms));
debug(cur_perms);
const int INF = int(1e9);
tuple<int, int, int, int, int> best_move = tuple(0, 0, 0, 0, 0);
int best_score = INF;
const int reps = int(1e4) / ssize(cur_perms);
REP (rep, reps) {
if (rep % 10 == 0)
debug(rep);
int type = rd(0, 3);
vector<int> tym(N);
iota(tym.begin(), tym.end(), 0);
shuffle(tym.begin(), tym.end(), rng);
auto move = tuple(type, tym[0], tym[1], tym[2], tym[3]);
auto [ra, rb, rc] = apply_move(cur_perms, move);
int score = max({ssize(ra), ssize(rb), ssize(rc)});
if (score < best_score) {
best_score = score;
best_move = move;
}
}
auto [na, nb, nc] = apply_move(cur_perms, best_move);
auto [type, a, b, c, d] = best_move;
debug(na);
debug(nb);
debug(nc);
debug(best_score);
++a;
++b;
++c;
++d;
debug(type, a, b, c, d);
int w;
if (type == 0)
w = getLightest(a, b, c);
else if (type == 1)
w = getMedian(a, b, c);
else if (type == 2)
w = getHeaviest(a, b, c);
else
w = getNextLightest(a, b, c, d);
debug(w);
if (w == a)
cur_perms = na;
else if (w == b)
cur_perms = nb;
else
cur_perms = nc;
}
debug(cur_perms[0]);
int ans[6];
REP (i, 6)
ans[cur_perms[0][i]] = i + 1;
answer(ans);
}
#ifdef LOCAL
int main() {
cin.tie(0)->sync_with_stdio(0);
init(18);
mt19937 main_rng(38182);
per.resize(6);
iota(per.begin(), per.end(), 0);
REP (i, 18) {
shuffle(per.begin(), per.end(), main_rng);
debug(per);
query_cnt = 0;
orderCoins();
cerr << "Asked_queries: " << query_cnt << endl;
}
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
255 ms |
480 KB |
Output is partially correct |
2 |
Partially correct |
281 ms |
504 KB |
Output is partially correct |
3 |
Partially correct |
263 ms |
480 KB |
Output is partially correct |
4 |
Partially correct |
252 ms |
488 KB |
Output is partially correct |
5 |
Partially correct |
257 ms |
480 KB |
Output is partially correct |
6 |
Partially correct |
273 ms |
484 KB |
Output is partially correct |
7 |
Partially correct |
259 ms |
612 KB |
Output is partially correct |
8 |
Partially correct |
261 ms |
492 KB |
Output is partially correct |
9 |
Partially correct |
258 ms |
484 KB |
Output is partially correct |
10 |
Partially correct |
262 ms |
488 KB |
Output is partially correct |
11 |
Partially correct |
260 ms |
468 KB |
Output is partially correct |
12 |
Partially correct |
255 ms |
484 KB |
Output is partially correct |
13 |
Partially correct |
256 ms |
480 KB |
Output is partially correct |
14 |
Partially correct |
254 ms |
484 KB |
Output is partially correct |
15 |
Partially correct |
265 ms |
476 KB |
Output is partially correct |
16 |
Partially correct |
252 ms |
484 KB |
Output is partially correct |
17 |
Partially correct |
257 ms |
480 KB |
Output is partially correct |
18 |
Partially correct |
300 ms |
484 KB |
Output is partially correct |
19 |
Partially correct |
269 ms |
488 KB |
Output is partially correct |
20 |
Partially correct |
253 ms |
480 KB |
Output is partially correct |
21 |
Partially correct |
270 ms |
480 KB |
Output is partially correct |
22 |
Partially correct |
279 ms |
468 KB |
Output is partially correct |
23 |
Partially correct |
252 ms |
468 KB |
Output is partially correct |
24 |
Partially correct |
265 ms |
464 KB |
Output is partially correct |
25 |
Partially correct |
251 ms |
476 KB |
Output is partially correct |
26 |
Partially correct |
263 ms |
488 KB |
Output is partially correct |
27 |
Partially correct |
256 ms |
472 KB |
Output is partially correct |
28 |
Partially correct |
260 ms |
488 KB |
Output is partially correct |
29 |
Partially correct |
255 ms |
480 KB |
Output is partially correct |
30 |
Partially correct |
256 ms |
488 KB |
Output is partially correct |
31 |
Partially correct |
265 ms |
480 KB |
Output is partially correct |
32 |
Partially correct |
255 ms |
472 KB |
Output is partially correct |
33 |
Partially correct |
258 ms |
484 KB |
Output is partially correct |
34 |
Partially correct |
264 ms |
492 KB |
Output is partially correct |
35 |
Partially correct |
248 ms |
468 KB |
Output is partially correct |
36 |
Correct |
255 ms |
480 KB |
Output is correct |
37 |
Partially correct |
254 ms |
464 KB |
Output is partially correct |
38 |
Partially correct |
257 ms |
484 KB |
Output is partially correct |
39 |
Partially correct |
265 ms |
600 KB |
Output is partially correct |
40 |
Partially correct |
258 ms |
484 KB |
Output is partially correct |