#include "scales.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int limit[6] {243,81,27,9,3,1};
int check(vector<int> perm, int a, int b, int c, int d, int op) {
vector<int> v;
int cnt = 0, x = 1;
for(auto i: perm)
if(i==a||i==b||i==c) {
if(x) v.push_back(i), x = 0;
if(++cnt==op)
return i;
} else if(i==d) {
x = 1;
}
return v.back();
}
inline int get(int a,int b, int c, int d, int op) {
switch(op) {
case 1: return getLightest(a,b,c);
case 2: return getMedian(a,b,c);
case 3: return getHeaviest(a,b,c);
default: return getNextLightest(a,b,c,d);
}
}
map<vector<vector<int>>, vector<int>> which;
bool ok(vector<vector<int>> poss, int x = 0) {
if(poss.size()<2) return 1;
for(int i = 1; i < 5; i++)
for(int j = i+1; j < 6; j++)
for(int k = j+1; k < 7; k++)
for(int op = 5; --op;) {
for(int d = 7; d--;) {
if(d==i||d==j||d==k) continue;
if(!d&&op>3) continue;
if(d&&op<4) continue;
vector<vector<int>> split[7];
for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
int Y = 0;
for(auto v:split)
Y = max(Y, (int)v.size());
if(Y<=limit[x]) {
if(ok(split[i], x+1)&&ok(split[j],x+1)&&ok(split[k],x+1))
return which[poss]=(vector<int>{i,j,k,op,d}), 1;
}
}
}
return 0;
}
int X[6];
int* dfs(vector<vector<int>> poss, int x = 0) {
if(poss.size()==1) {
for(int i =0; i < 6; i++)
X[i] = poss[0][i];
return X;
}
vector<int> v = which[poss];
int i = v[0],j = v[1],k = v[2],op = v[3],d = v[4];
vector<vector<int>> split[7];
for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
return dfs(split[get(i,j,k,d,op)], x+1);
}
void init(int T) {
vector<vector<int>> v;
vector<int> x {1,2,3,4,5,6};
do
v.push_back(x);
while(next_permutation(x.begin(), x.end()));
ok(v);
}
void orderCoins(){
vector<vector<int>> v;
vector<int> x {1,2,3,4,5,6};
do
v.push_back(x);
while(next_permutation(x.begin(), x.end()));
answer(dfs(v));
}
Compilation message
scales.cpp: In function 'int* dfs(std::vector<std::vector<int> >, int)':
scales.cpp:61:14: warning: declaration of 'v' shadows a previous local [-Wshadow]
61 | for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
| ^
scales.cpp:58:17: note: shadowed declaration is here
58 | vector<int> v = which[poss];
| ^
scales.cpp: In function 'void init(int)':
scales.cpp:64:15: warning: unused parameter 'T' [-Wunused-parameter]
64 | void init(int T) {
| ~~~~^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
800 KB |
Output is correct |
2 |
Correct |
56 ms |
772 KB |
Output is correct |
3 |
Correct |
53 ms |
788 KB |
Output is correct |
4 |
Correct |
64 ms |
712 KB |
Output is correct |
5 |
Correct |
67 ms |
716 KB |
Output is correct |
6 |
Correct |
54 ms |
724 KB |
Output is correct |
7 |
Correct |
53 ms |
716 KB |
Output is correct |
8 |
Correct |
53 ms |
724 KB |
Output is correct |
9 |
Correct |
53 ms |
716 KB |
Output is correct |
10 |
Correct |
54 ms |
748 KB |
Output is correct |
11 |
Correct |
53 ms |
832 KB |
Output is correct |
12 |
Correct |
53 ms |
820 KB |
Output is correct |
13 |
Correct |
66 ms |
820 KB |
Output is correct |
14 |
Correct |
53 ms |
784 KB |
Output is correct |
15 |
Correct |
54 ms |
724 KB |
Output is correct |
16 |
Correct |
57 ms |
764 KB |
Output is correct |
17 |
Correct |
53 ms |
716 KB |
Output is correct |
18 |
Correct |
63 ms |
732 KB |
Output is correct |
19 |
Correct |
65 ms |
732 KB |
Output is correct |
20 |
Correct |
65 ms |
712 KB |
Output is correct |
21 |
Correct |
53 ms |
708 KB |
Output is correct |
22 |
Correct |
66 ms |
708 KB |
Output is correct |
23 |
Correct |
54 ms |
704 KB |
Output is correct |
24 |
Correct |
53 ms |
748 KB |
Output is correct |
25 |
Correct |
54 ms |
772 KB |
Output is correct |
26 |
Correct |
66 ms |
820 KB |
Output is correct |
27 |
Correct |
63 ms |
824 KB |
Output is correct |
28 |
Correct |
53 ms |
732 KB |
Output is correct |
29 |
Correct |
54 ms |
760 KB |
Output is correct |
30 |
Correct |
62 ms |
748 KB |
Output is correct |
31 |
Correct |
54 ms |
772 KB |
Output is correct |
32 |
Correct |
54 ms |
732 KB |
Output is correct |
33 |
Correct |
53 ms |
764 KB |
Output is correct |
34 |
Correct |
62 ms |
760 KB |
Output is correct |
35 |
Correct |
70 ms |
716 KB |
Output is correct |
36 |
Correct |
69 ms |
764 KB |
Output is correct |
37 |
Correct |
53 ms |
828 KB |
Output is correct |
38 |
Correct |
59 ms |
712 KB |
Output is correct |
39 |
Correct |
55 ms |
708 KB |
Output is correct |
40 |
Correct |
68 ms |
716 KB |
Output is correct |