제출 #669212

#제출 시각아이디문제언어결과실행 시간메모리
669212alvingogo저울 (IOI15_scales)C++14
100 / 100
117 ms624 KiB
#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; int dfs(vector<int>& x,int s); map<vector<int>,array<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==-2){ for(int i=5;i>=0;i--){ if(g[i]==a || g[i]==b || g[i]==c){ return g[i]; } } } else if(t==-3){ 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; } inline int cal(vector<int>& x,int t,int i,int j,int k,int s){ vector<int> b,c,d; for(auto y:x){ auto h=z[y]; int a=get(h,i,j,k,t); if(a==i){ b.push_back(y); } else if(a==j){ c.push_back(y); } else{ d.push_back(y); } } if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){ return 0; } 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(s<0 || x.size()>po[s]){ return 0; } else if(mp.find(x)!=mp.end()){ if(mp[x][0]==-1){ return 0; } else{ return 1; } } else if(s==0){ 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,s)){ mp[x]={i,j,k,t}; return 1; } } } } } } mp[x]={-1,-1,-1,-1}; return 0; } void init(int T){ vector<int> g(6); 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]==-3){ y=fm(h[0],h[1],h[2]); } else if(h[3]==-2){ 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; } int ans[6]; for(int i=0;i<6;i++){ ans[i]=z[g[0]][i]+1; } answer(ans); }

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'int cal(std::vector<int>&, int, int, int, int, int)':
scales.cpp:80:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
      |        ~~~~~~~~^~~~~~~~
scales.cpp:80:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
      |                            ~~~~~~~~^~~~~~~~
scales.cpp:80:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
      |                                                ~~~~~~~~^~~~~~~~
scales.cpp: In function 'int dfs(std::vector<int>&, int)':
scales.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |     if(s<0 || x.size()>po[s]){
      |               ~~~~~~~~^~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:120:15: warning: unused parameter 'T' [-Wunused-parameter]
  120 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'int get(std::vector<int>, int, int, int, int)':
scales.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...