This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "scales.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
map<vector<int>,vector<int>(4)> mp;
int po[7]={1,3,9,27,81,243,729};
vector<vector<int> > z;
int get(vector<int> g,int a,int b,int c,int t){
if(t==-1){
for(int i=0;i<6;i++){
if(g[i]==a || g[i]==b || g[i]==c){
return g[i];
}
}
}
else if(t==-3){
for(int i=5;i>=0;i--){
if(g[i]==a || g[i]==b || g[i]==c){
return g[i];
}
}
}
else if(t==-2){
int cnt=0;
for(int i=0;i<6;i++){
if(g[i]==a || g[i]==b || g[i]==c){
cnt++;
}
if(cnt==2){
return g[i];
}
}
}
else{
int cnt=0;
for(int i=0;i<6;i++){
if(g[i]==t){
cnt++;
}
if(cnt && (g[i]==a || g[i]==b || g[i]==c)){
return g[i];
}
}
return get(g,a,b,c,-1);
}
}
int fg(int a,int b,int c){
return getHeaviest(a+1,b+1,c+1)-1;
}
int fm(int a,int b,int c){
return getMedian(a+1,b+1,c+1)-1;
}
int fl(int a,int b,int c){
return getLightest(a+1,b+1,c+1)-1;
}
int nx(int a,int b,int c,int d){
return getNextLightest(a+1,b+1,c+1,d+1)-1;
}
int cal(vector<int>& x,int t,int i,int j,int k){
vector<int> b,c,d;
for(auto y:x){
auto h=z[x];
int a=get(h,i,j,k,t);
if(a==i){
b.push_back(h);
}
else if(a==j){
c.push_back(h);
}
else{
d.push_back(h);
}
}
if(dfs(b,s-1) && dfs(c,s-1) && dfs(d,s-1)){
return 1;
}
return 0;
}
int dfs(vector<int>& x,int s){
if(x.size()>po[s]){
return 1;
}
else if(mp.find(x)!=mp.end()){
if(mp[x][0]==-1){
return 0;
}
else{
return 1;
}
}
for(int i=0;i<4;i++){
for(int j=i+1;j<5;j++){
for(int k=j+1;k<6;k++){
for(int t=-3;t<6;t++){
if(t!=i && t!=j && t!=k){
if(cal(x,t,i,j,k)){
return mp[x]={i,j,k,t};
}
}
}
}
}
}
return mp[x]={-1,-1,-1,-1};
}
void init(int T){
vector<int> g(n);
iota(g.begin(),g.end(),0);
for(int i=0;i<720;i++){
z.push_back(g);
next_permutation(g.begin(),g.end());
}
vector<int> k(720);
iota(k.begin(),k.end(),0);
dfs(k,6);
}
void orderCoins(){
vector<int> g(720);
iota(g.begin(),g.end(),0);
while(g.size()>1){
auto h=mp[g];
vector<int> nw;
int y;
if(h[3]==-1){
y=fl(h[0],h[1],h[2]);
}
else if(h[3]==-2){
y=fm(h[0],h[1],h[2]);
}
else if(h[3]==-3){
y=fg(h[0],h[1],h[2]);
}
else{
y=nx(h[0],h[1],h[2],h[3]);
}
for(auto r:g){
if(get(z[r],h[0],h[1],h[2],h[3])==y){
nw.push_back(r);
}
}
g=nw;
}
answer(g);
}
Compilation message (stderr)
scales.cpp:10:17: error: temporary of non-literal type 'std::vector<int>' in a constant expression
10 | map<vector<int>,vector<int>(4)> mp;
| ^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from scales.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'std::vector<int>' is not literal because:
389 | class vector : protected _Vector_base<_Tp, _Alloc>
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'std::vector<int>' has a non-trivial destructor
scales.cpp:10:31: error: type/value mismatch at argument 2 in template parameter list for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'
10 | map<vector<int>,vector<int>(4)> mp;
| ^
scales.cpp:10:31: note: expected a type, got 'std::vector<int>(4, std::allocator<int>())'
scales.cpp:10:31: error: template argument 4 is invalid
scales.cpp: In function 'int cal(std::vector<int>&, int, int, int, int)':
scales.cpp:67:17: error: no match for 'operator[]' (operand types are 'std::vector<std::vector<int> >' and 'std::vector<int>')
67 | auto h=z[x];
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from scales.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1043:7: note: candidate: 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::reference = std::vector<int>&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
1043 | operator[](size_type __n) _GLIBCXX_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1043:28: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'}
1043 | operator[](size_type __n) _GLIBCXX_NOEXCEPT
| ~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1061:7: note: candidate: 'std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) const [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::const_reference = const std::vector<int>&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
1061 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1061:28: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'}
1061 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT
| ~~~~~~~~~~^~~
scales.cpp:66:14: warning: unused variable 'y' [-Wunused-variable]
66 | for(auto y:x){
| ^
scales.cpp:79:14: error: 's' was not declared in this scope
79 | if(dfs(b,s-1) && dfs(c,s-1) && dfs(d,s-1)){
| ^
scales.cpp:79:8: error: 'dfs' was not declared in this scope; did you mean 'ffs'?
79 | if(dfs(b,s-1) && dfs(c,s-1) && dfs(d,s-1)){
| ^~~
| ffs
scales.cpp: In function 'int dfs(std::vector<int>&, int)':
scales.cpp:85:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
85 | if(x.size()>po[s]){
| ~~~~~~~~^~~~~~
scales.cpp:88:16: error: request for member 'find' in 'mp', which is of non-class type 'int'
88 | else if(mp.find(x)!=mp.end()){
| ^~~~
scales.cpp:88:28: error: request for member 'end' in 'mp', which is of non-class type 'int'
88 | else if(mp.find(x)!=mp.end()){
| ^~~
scales.cpp:89:14: error: no match for 'operator[]' (operand types are 'int' and 'std::vector<int>')
89 | if(mp[x][0]==-1){
| ^
scales.cpp:102:38: error: no match for 'operator[]' (operand types are 'int' and 'std::vector<int>')
102 | return mp[x]={i,j,k,t};
| ^
scales.cpp:109:14: error: no match for 'operator[]' (operand types are 'int' and 'std::vector<int>')
109 | return mp[x]={-1,-1,-1,-1};
| ^
scales.cpp: In function 'void init(int)':
scales.cpp:112:19: error: 'n' was not declared in this scope
112 | vector<int> g(n);
| ^
scales.cpp:111:15: warning: unused parameter 'T' [-Wunused-parameter]
111 | void init(int T){
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:126:18: error: no match for 'operator[]' (operand types are 'int' and 'std::vector<int>')
126 | auto h=mp[g];
| ^
scales.cpp:148:12: error: cannot convert 'std::vector<int>' to 'int*'
148 | answer(g);
| ^
| |
| std::vector<int>
In file included from scales.cpp:2:
scales.h:10:17: note: initializing argument 1 of 'void answer(int*)'
10 | void answer(int W[]);
| ~~~~^~~
scales.cpp: In function 'int get(std::vector<int>, int, int, int, int)':
scales.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
51 | }
| ^