| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133172 |
2019-07-20T08:30:21 Z |
MAMBA |
Scales (IOI15_scales) |
C++17 |
|
1000 ms |
12920 KB |
#include "scales.h"
#include <bits/stdc++.h>
// getheaviest
// getLightest
// getMedian
// getNextLightest
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
typedef array<int , 6> ar;
typedef vector<int> vi;
struct dt {
int n = 1e9;
int nxt = -1;
int A = -1, B = -1, C = -1, D = -1;
dt() {}
dt(int N , int Nxt , int a , int b, int c , int d = -1) {
n = N, nxt = Nxt , A = a, B = b, C = c, D = d;
}
};
ar per[720];
map<vi , dt> mp;
inline void R0(vi &v , int A , int B , int C, int R) {
vi res;
for (auto e : v)
if (max({per[e][A] , per[e][B] , per[e][C]}) <= per[e][R])
res.pb(e);
v = res;
}
inline void R1(vi &v , int A , int B , int C, int R) {
vi res;
for (auto e : v)
if (min({per[e][A] , per[e][B] , per[e][C]}) >= per[e][R])
res.pb(e);
v = res;
}
inline void R2(vi &v , int A , int B , int C, int R) {
vi res;
for (auto e : v)
if (min({per[e][A] , per[e][B] , per[e][C]}) < per[e][R] &&
max({per[e][A] , per[e][B] , per[e][C]}) > per[e][R])
res.pb(e);
v = res;
}
inline void R3(vi &v , int A , int B , int C, int D, int R) {
vi res;
for (auto e : v) {
if (max({per[e][A] , per[e][B] , per[e][C]}) < per[e][D]) {
if (min({per[e][A] , per[e][B] , per[e][C]}) == per[e][R])
res.pb(e);
}
else {
bool flag = false;
if (per[e][A] > per[e][D] && per[e][A] < per[e][R]) flag = true;
if (per[e][B] > per[e][D] && per[e][B] < per[e][R]) flag = true;
if (per[e][C] > per[e][D] && per[e][C] < per[e][R]) flag = true;
if (!flag)
res.pb(e);
}
}
v = res;
}
bool ok[4] = {1 , 0 , 1 , 0};
map<vi , int> last_try;
bool dfs(vi me, int exp = 1e9) {
if (last_try.count(me) && last_try[me] >= exp)
return false;
int cnt = 0;
int ww = 1;
while (ww < me.size()) {
ww *= 3;
cnt++;
}
if (cnt > exp) {
last_try[me] = exp;
return false;
}
if (me.size() == 1) {
mp[me] = dt(0 , -1 , -1, -1, -1);
return true;
}
dt ans(exp + 1 , -1 , -1 , -1, -1);
if (ok[0]) {// 0
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6) {
vi a = me;
vi b = me;
vi c = me;
R0(a , i , j , k , i);
R0(b , i , j , k , j);
R0(c , i , j , k , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 0 , i , j , k);
}
}
if (ok[1]) {// 1
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6) {
vi a = me;
vi b = me;
vi c = me;
R1(a , i , j , k , i);
R1(b , i , j , k , j);
R1(c , i , j , k , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 1 , i , j , k);
}
}
if (ok[2]) {// 2
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6) {
vi a = me;
vi b = me;
vi c = me;
R2(a , i , j , k , i);
R2(b , i , j , k , j);
R2(c , i , j , k , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 2 , i , j , k);
}
}
if (ok[3]) {// 3
rep(i , 0 , 6)
rep(j , i + 1 , 6)
rep(k , j + 1 , 6)
rep(z , k + 1, 6) {
vi a = me;
vi b = me;
vi c = me;
R3(a , i , j , k , z , i);
R3(b , i , j , k , z , j);
R3(c , i , j , k , z , k);
int wor = -10;
if (max({a.size() , b.size() , c.size()}) == me.size()) continue;
if (mp.count(a)) wor = max(wor , mp[a].n);
if (mp.count(b)) wor = max(wor , mp[b].n);
if (mp.count(c)) wor = max(wor , mp[c].n);
if (wor + 1 < ans.n && !mp.count(a)) {
if (dfs(a , ans.n - 2))
wor = max(wor , mp[a].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(b)) {
if (dfs(b , ans.n - 2))
wor = max(wor , mp[b].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n && !mp.count(c)) {
if (dfs(c , ans.n - 2))
wor = max(wor , mp[c].n);
else
wor = 1e9;
}
if (wor + 1 < ans.n)
ans = dt(wor + 1 , 3 , i , j , k, z);
}
}
if (ans.nxt == -1) {
last_try[me] = exp;
return false;
}
mp[me] = ans;
return true;
}
void init(int T) {
mp.clear();
mp[vi()] = dt(0 , -1 , -1 , -1, -1);
ar tmp = {0 , 1 , 2 , 3 , 4, 5};
rep(i , 0 , 720) {
per[i] = tmp;
next_permutation(tmp.begin(), tmp.end());
}
vi st(720);
iota(st.begin(), st.end() , 0);
dfs(st);
}
void orderCoins() {
vi st(720);
iota(st.begin(), st.end() , 0);
while (st.size() > 1) {
dt me = mp[st];
int tp = me.nxt;
assert(~tp);
if (tp == 0) {
int res = getHeaviest(me.A + 1 , me.B + 1 , me.C + 1) - 1;
R0(st , me.A , me.B , me.C , res);
}
if (tp == 1) {
int res = getLightest(me.A + 1, me.B + 1 , me.C + 1) - 1;
R1(st , me.A , me.B , me.C , res);
}
if (tp == 2) {
int res = getMedian(me.A + 1 , me.B + 1 , me.C + 1) - 1;
R2(st , me.A , me.B , me.C , res);
}
if (tp == 3) {
int res = getNextLightest(me.A + 1, me.B + 1 , me.C + 1, me.D + 1) - 1;
R3(st , me.A , me.B , me.C , me.D , res);
}
}
int w[6];
rep(i , 0 , 6)
w[per[st[0]][i]] = i + 1;
answer(w);
}
Compilation message
scales.cpp: In function 'bool dfs(vi, int)':
scales.cpp:87:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ww < me.size()) {
~~~^~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:292:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
12556 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1071 ms |
12280 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1067 ms |
12572 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1086 ms |
12920 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1082 ms |
12536 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1061 ms |
12132 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1074 ms |
12104 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1082 ms |
12616 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1080 ms |
12660 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1070 ms |
12056 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1071 ms |
12476 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1070 ms |
12408 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1071 ms |
12416 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1084 ms |
12664 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1064 ms |
12336 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1074 ms |
12612 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1083 ms |
12408 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1077 ms |
12676 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1078 ms |
12484 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1086 ms |
12408 KB |
Time limit exceeded |
| 21 |
Execution timed out |
1079 ms |
12352 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1066 ms |
12532 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1079 ms |
12536 KB |
Time limit exceeded |
| 24 |
Execution timed out |
1077 ms |
12632 KB |
Time limit exceeded |
| 25 |
Execution timed out |
1085 ms |
12664 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1082 ms |
12640 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1084 ms |
12696 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1074 ms |
12700 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1087 ms |
12792 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1074 ms |
12536 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1084 ms |
12536 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1059 ms |
12356 KB |
Time limit exceeded |
| 33 |
Execution timed out |
1066 ms |
12516 KB |
Time limit exceeded |
| 34 |
Execution timed out |
1086 ms |
12664 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1079 ms |
12296 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1064 ms |
12224 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1085 ms |
12804 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1072 ms |
12196 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1070 ms |
12428 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1076 ms |
12572 KB |
Time limit exceeded |
