| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 287654 |
2020-08-31T21:57:29 Z |
Saboon |
Scales (IOI15_scales) |
C++17 |
|
20 ms |
5632 KB |
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
int P[720][6], p[6], dp[720 + 10];
vector<int> per[100*720 + 100], t[100*720 + 100];
int newint = 2;
vector<int> Q[100*720+100];
int getMax(int x, int i, int j, int k){
for (int idx = 5; idx >= 0; idx--)
if (P[x][idx] == i or P[x][idx] == j or P[x][idx] == k)
return P[x][idx];
}
int getMin(int x, int i, int j, int k){
for (int idx = 0; idx <= 5; idx++)
if (P[x][idx] == i or P[x][idx] == j or P[x][idx] == k)
return P[x][idx];
}
int getMid(int x, int i, int j, int k){
bool found = 0;
for (int idx = 5; idx >= 0; idx--){
if (P[x][idx] == i or P[x][idx] == j or P[x][idx] == k){
if (found)
return P[x][idx];
else
found = 1;
}
}
}
int getNext(int x, int i, int j, int k, int z){
bool found = 0;
for (int idx = 0; idx <= 5; idx++){
if (P[x][idx] == z)
found = true;
if ((P[x][idx] == i or P[x][idx] == j or P[x][idx] == k) and found == true)
return P[x][idx];
}
return getMin(x, i, j, k);
}
bool dfs(int v, int h = 0){
if (per[v].size() <= 1)
return true;
int cnt = per[v].size();
for (int i = 1; i <= 6; i++){
for (int j = i+1; j <= 6; j++){
for (int k = j+1; k <= 6; k++){
int a = 0, b = 0, c = 0;
for (auto x : per[v]){
if (getMax(x, i, j, k) == i)
a ++;
else if (getMax(x, i, j, k) == j)
b ++;
else
c ++;
}
if (dp[max({a,b,c})]+h+1 <= 6){
Q[v] = {1, i, j, k};
int q = newint;
newint += 3;
t[v] = {q, q+1, q+2};
for (auto x : per[v]){
if (getMax(x, i, j, k) == i)
per[q].push_back(x);
else if (getMax(x, i, j, k) == j)
per[q+1].push_back(x);
else
per[q+2].push_back(x);
}
bool ret = (dfs(q, h+1) and dfs(q+1, h+1) and dfs(q+2, h+1));
if (ret == 1)
return true;
per[q].clear(), per[q+1].clear(), per[q+2].clear();
newint -= 3;
}
a = 0, b = 0, c = 0;
for (auto x : per[v]){
if (getMin(x, i, j, k) == i)
a ++;
else if (getMin(x, i, j, k) == j)
b ++;
else
c ++;
}
if (dp[max({a,b,c})]+h+1 <= 6){
Q[v] = {2, i, j, k};
int q = newint;
newint += 3;
t[v] = {q, q+1, q+2};
for (auto x : per[v]){
if (getMin(x, i, j, k) == i)
per[q].push_back(x);
else if (getMin(x, i, j, k) == j)
per[q+1].push_back(x);
else
per[q+2].push_back(x);
}
bool ret = (dfs(q, h+1) and dfs(q+1, h+1) and dfs(q+2, h+1));
if (ret == 1)
return true;
per[q].clear(), per[q+1].clear(), per[q+2].clear();
newint -= 3;
}
a = 0, b = 0, c = 0;
for (auto x : per[v]){
if (getMid(x, i, j, k) == i)
a ++;
else if (getMid(x, i, j, k) == j)
b ++;
else
c ++;
}
if (dp[max({a,b,c})]+h+1 <= 6){
Q[v] = {3, i, j, k};
int q = newint;
newint += 3;
t[v] = {q, q+1, q+2};
for (auto x : per[v]){
if (getMid(x, i, j, k) == i)
per[q].push_back(x);
else if (getMid(x, i, j, k) == j)
per[q+1].push_back(x);
else
per[q+2].push_back(x);
}
bool ret = (dfs(q, h+1) and dfs(q+1, h+1) and dfs(q+2, h+1));
if (ret == 1)
return true;
per[q].clear(), per[q+1].clear(), per[q+2].clear();
newint -= 3;
}
for (int z = 1; z <= 6; z++){
if (z == i or z == j or z == k)
continue;
a = 0, b = 0, c = 0;
for (auto x : per[v]){
if (getNext(x, i, j, k, z) == i)
a ++;
else if (getNext(x, i, j, k, z) == j)
b ++;
else
c ++;
}
if (dp[max({a,b,c})]+h+1 <= 6){
Q[v] = {4, i, j, k, z};
int q = newint;
newint += 3;
t[v] = {q, q+1, q+2};
for (auto x : per[v]){
if (getNext(x, i, j, k, z) == i)
per[q].push_back(x);
else if (getNext(x, i, j, k, z) == j)
per[q+1].push_back(x);
else
per[q+2].push_back(x);
}
bool ret = (dfs(q, h+1) and dfs(q+1, h+1) and dfs(q+2, h+1));
if (ret == 1)
return true;
per[q].clear(), per[q+1].clear(), per[q+2].clear();
newint -= 3;
}
}
}
}
}
return false;
}
void init(int T){
for (int i = 0; i < 6; i++)
p[i] = i+1;
int cnt = 0;
do{
for (int i = 0; i < 6; i++)
P[cnt][i] = p[i];
cnt ++;
} while(next_permutation(p,p+6));
int root = 1;
for (int i = 0; i < cnt; i++)
per[root].push_back(i);
dp[1] = 0;
for (int i = 2; i <= 720; i++)
dp[i] = dp[(i+2)/3] + 1;
assert(dfs(root) == true);
}
void orderCoins(){
int v = 1;
while (per[v].size() > 1){
if (Q[v][0] == 1){
int x = getHeaviest(Q[v][1], Q[v][2], Q[v][3]);
if (x == Q[v][1])
v = t[v][0];
else if (x == Q[v][2])
v = t[v][1];
else
v = t[v][2];
}
else if (Q[v][0] == 2){
int x = getLightest(Q[v][1], Q[v][2], Q[v][3]);
if (x == Q[v][1])
v = t[v][0];
else if (x == Q[v][2])
v = t[v][1];
else
v = t[v][2];
}
else if (Q[v][0] == 3){
int x = getMedian(Q[v][1], Q[v][2], Q[v][3]);
if (x == Q[v][1])
v = t[v][0];
else if (x == Q[v][2])
v = t[v][1];
else
v = t[v][2];
}
else{
int x = getNextLightest(Q[v][1], Q[v][2], Q[v][3], Q[v][4]);
if (x == Q[v][1])
v = t[v][0];
else if (x == Q[v][2])
v = t[v][1];
else
v = t[v][2];
}
}
assert(per[v].size() == 1);
answer(P[per[v][0]]);
}
Compilation message
scales.cpp: In function 'bool dfs(int, int)':
scales.cpp:48:23: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
48 | int cnt = per[v].size();
| ~~~~~~~~~~~^~
scales.cpp:48:6: warning: unused variable 'cnt' [-Wunused-variable]
48 | int cnt = per[v].size();
| ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:177:15: warning: unused parameter 'T' [-Wunused-parameter]
177 | void init(int T){
| ~~~~^
scales.cpp: In function 'int getMax(int, int, int, int)':
scales.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
14 | }
| ^
scales.cpp: In function 'int getMin(int, int, int, int)':
scales.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
20 | }
| ^
scales.cpp: In function 'int getMid(int, int, int, int)':
scales.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
32 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 4 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 6 |
Correct |
19 ms |
5632 KB |
Output is correct |
| 7 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 8 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 9 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 10 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 11 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 12 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 13 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 14 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 15 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 16 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 17 |
Correct |
19 ms |
5632 KB |
Output is correct |
| 18 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 19 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 20 |
Correct |
20 ms |
5504 KB |
Output is correct |
| 21 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 22 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 23 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 24 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 25 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 26 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 27 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 28 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 29 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 30 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 31 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 32 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 33 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 34 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 35 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 36 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 37 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 38 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 39 |
Correct |
20 ms |
5504 KB |
Output is correct |
| 40 |
Correct |
19 ms |
5504 KB |
Output is correct |
