# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
831897 |
2023-08-20T17:05:59 Z |
Asymmetry |
Scales (IOI15_scales) |
C++17 |
|
1000 ms |
588 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);
tuple<int, int, int> best_score = tuple(INF, INF, INF);
const int reps = ssize(cur_perms) == 720 ? 1 : int(1e5) / ssize(cur_perms);
REP (rep, reps) {
int type = rd(0, 3);
if (reps == 1)
type = rd(0, 2);
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);
vector<int> xd = {ssize(ra), ssize(rb), ssize(rc)};
sort(xd.rbegin(), xd.rend());
auto score = tuple(xd[0], xd[1], xd[2]);
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, 100) {
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 |
Execution timed out |
1084 ms |
484 KB |
Time limit exceeded |
2 |
Execution timed out |
1080 ms |
480 KB |
Time limit exceeded |
3 |
Execution timed out |
1080 ms |
468 KB |
Time limit exceeded |
4 |
Execution timed out |
1075 ms |
484 KB |
Time limit exceeded |
5 |
Execution timed out |
1093 ms |
484 KB |
Time limit exceeded |
6 |
Execution timed out |
1014 ms |
448 KB |
Time limit exceeded |
7 |
Execution timed out |
1063 ms |
476 KB |
Time limit exceeded |
8 |
Execution timed out |
1043 ms |
476 KB |
Time limit exceeded |
9 |
Execution timed out |
1085 ms |
480 KB |
Time limit exceeded |
10 |
Execution timed out |
1082 ms |
448 KB |
Time limit exceeded |
11 |
Execution timed out |
1083 ms |
480 KB |
Time limit exceeded |
12 |
Execution timed out |
1085 ms |
476 KB |
Time limit exceeded |
13 |
Execution timed out |
1066 ms |
484 KB |
Time limit exceeded |
14 |
Execution timed out |
1056 ms |
476 KB |
Time limit exceeded |
15 |
Execution timed out |
1091 ms |
476 KB |
Time limit exceeded |
16 |
Execution timed out |
1062 ms |
476 KB |
Time limit exceeded |
17 |
Execution timed out |
1079 ms |
476 KB |
Time limit exceeded |
18 |
Execution timed out |
1075 ms |
448 KB |
Time limit exceeded |
19 |
Execution timed out |
1086 ms |
480 KB |
Time limit exceeded |
20 |
Execution timed out |
1081 ms |
476 KB |
Time limit exceeded |
21 |
Execution timed out |
1084 ms |
448 KB |
Time limit exceeded |
22 |
Execution timed out |
1073 ms |
484 KB |
Time limit exceeded |
23 |
Execution timed out |
1074 ms |
448 KB |
Time limit exceeded |
24 |
Execution timed out |
1082 ms |
480 KB |
Time limit exceeded |
25 |
Execution timed out |
1068 ms |
448 KB |
Time limit exceeded |
26 |
Execution timed out |
1082 ms |
468 KB |
Time limit exceeded |
27 |
Execution timed out |
1070 ms |
484 KB |
Time limit exceeded |
28 |
Execution timed out |
1064 ms |
468 KB |
Time limit exceeded |
29 |
Execution timed out |
1069 ms |
476 KB |
Time limit exceeded |
30 |
Execution timed out |
1080 ms |
588 KB |
Time limit exceeded |
31 |
Execution timed out |
1088 ms |
476 KB |
Time limit exceeded |
32 |
Execution timed out |
1080 ms |
460 KB |
Time limit exceeded |
33 |
Execution timed out |
1081 ms |
460 KB |
Time limit exceeded |
34 |
Execution timed out |
1087 ms |
484 KB |
Time limit exceeded |
35 |
Execution timed out |
1079 ms |
476 KB |
Time limit exceeded |
36 |
Execution timed out |
1080 ms |
480 KB |
Time limit exceeded |
37 |
Execution timed out |
1079 ms |
472 KB |
Time limit exceeded |
38 |
Execution timed out |
1082 ms |
468 KB |
Time limit exceeded |
39 |
Execution timed out |
1041 ms |
480 KB |
Time limit exceeded |
40 |
Execution timed out |
1081 ms |
588 KB |
Time limit exceeded |