#include "scales.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
void init(int T) {}
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(!x) ok(poss);
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 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 'void init(int)':
scales.cpp:5:15: warning: unused parameter 'T' [-Wunused-parameter]
5 | void init(int T) {}
| ~~~~^
scales.cpp: In function 'int* dfs(std::vector<std::vector<int> >, int)':
scales.cpp:63:14: warning: declaration of 'v' shadows a previous local [-Wshadow]
63 | for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
| ^
scales.cpp:60:17: note: shadowed declaration is here
60 | vector<int> v = which[poss];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
858 ms |
912 KB |
Output is correct |
2 |
Correct |
864 ms |
864 KB |
Output is correct |
3 |
Correct |
863 ms |
908 KB |
Output is correct |
4 |
Correct |
856 ms |
844 KB |
Output is correct |
5 |
Correct |
870 ms |
920 KB |
Output is correct |
6 |
Correct |
871 ms |
944 KB |
Output is correct |
7 |
Correct |
858 ms |
904 KB |
Output is correct |
8 |
Correct |
875 ms |
912 KB |
Output is correct |
9 |
Correct |
870 ms |
920 KB |
Output is correct |
10 |
Correct |
859 ms |
920 KB |
Output is correct |
11 |
Correct |
885 ms |
916 KB |
Output is correct |
12 |
Correct |
878 ms |
932 KB |
Output is correct |
13 |
Correct |
860 ms |
892 KB |
Output is correct |
14 |
Correct |
922 ms |
916 KB |
Output is correct |
15 |
Correct |
860 ms |
924 KB |
Output is correct |
16 |
Correct |
859 ms |
916 KB |
Output is correct |
17 |
Correct |
863 ms |
844 KB |
Output is correct |
18 |
Correct |
858 ms |
944 KB |
Output is correct |
19 |
Correct |
872 ms |
840 KB |
Output is correct |
20 |
Correct |
883 ms |
904 KB |
Output is correct |
21 |
Correct |
877 ms |
920 KB |
Output is correct |
22 |
Correct |
870 ms |
1032 KB |
Output is correct |
23 |
Correct |
894 ms |
972 KB |
Output is correct |
24 |
Correct |
884 ms |
924 KB |
Output is correct |
25 |
Correct |
868 ms |
1016 KB |
Output is correct |
26 |
Correct |
877 ms |
920 KB |
Output is correct |
27 |
Correct |
881 ms |
1008 KB |
Output is correct |
28 |
Correct |
872 ms |
972 KB |
Output is correct |
29 |
Correct |
868 ms |
1012 KB |
Output is correct |
30 |
Correct |
881 ms |
804 KB |
Output is correct |
31 |
Correct |
869 ms |
936 KB |
Output is correct |
32 |
Correct |
872 ms |
1016 KB |
Output is correct |
33 |
Correct |
905 ms |
1012 KB |
Output is correct |
34 |
Correct |
887 ms |
1016 KB |
Output is correct |
35 |
Correct |
914 ms |
916 KB |
Output is correct |
36 |
Correct |
872 ms |
916 KB |
Output is correct |
37 |
Correct |
920 ms |
920 KB |
Output is correct |
38 |
Correct |
884 ms |
920 KB |
Output is correct |
39 |
Correct |
873 ms |
992 KB |
Output is correct |
40 |
Correct |
869 ms |
920 KB |
Output is correct |