Submission #678897

#TimeUsernameProblemLanguageResultExecution timeMemory
678897n0sk1llScales (IOI15_scales)C++14
75 / 100
119 ms480 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) (x).begin(),(x).end() #define inv(n) power((n), mod - 2) #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++) #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++) #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--) #define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--) #define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0) #define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow /*int jp[6]; int getLightest(int a, int b, int c) { int red=0; ff(i,0,6) { if (jp[i]==a || jp[i]==b || jp[i]==c) { if (red==0) { if (jp[i]==a) return a; if (jp[i]==b) return b; if (jp[i]==c) return c; } else red++; } } } int getMedian(int a, int b, int c) { int red=0; ff(i,0,6) { if (jp[i]==a || jp[i]==b || jp[i]==c) { if (red==1) { if (jp[i]==a) return a; if (jp[i]==b) return b; if (jp[i]==c) return c; } else red++; } } } int getHeaviest(int a, int b, int c) { int red=0; ff(i,0,6) { if (jp[i]==a || jp[i]==b || jp[i]==c) { if (red==2) { if (jp[i]==a) return a; if (jp[i]==b) return b; if (jp[i]==c) return c; } else red++; } } } int getNextLightest(int a, int b, int c, int d) { int red=69; ff(i,0,6) { if (jp[i]==d) red=0; if (jp[i]==a || jp[i]==b || jp[i]==c) { if (red==0) { if (jp[i]==a) return a; if (jp[i]==b) return b; if (jp[i]==c) return c; } else red++; } } ff(i,0,6) { if (jp[i]==a || jp[i]==b || jp[i]==c) { if (red==0) { if (jp[i]==a) return a; if (jp[i]==b) return b; if (jp[i]==c) return c; } else red++; } } } void answer(int* sta) { ff(i,0,6) cout<<jp[i]<<" "; cout<<endl; ff(i,0,6) cout<<sta[i]<<" "; cout<<endl; cout<<endl; }*/ #include "scales.h" vector<vector<int>> perms; void init(int T) { perms.clear(); vector<int> tperm={1,2,3,4,5,6}; do { perms.pb(tperm); } while (next_permutation(all(tperm))); } int evalmin(int a, int b, int c) { int ka=0,kb=0,kc=0; for (auto p : perms) { for (auto it : p) { if (it==a) {ka++; break;} if (it==b) {kb++; break;} if (it==c) {kc++; break;} } } return max(max(ka,kb),kc)-min(min(ka,kb),kc); } int evalmed(int a, int b, int c) { int ka=0,kb=0,kc=0; for (auto p : perms) { int red=0; for (auto it : p) { if (it==a) {if (red==1) {ka++; break;} else red++;} if (it==b) {if (red==1) {kb++; break;} else red++;} if (it==c) {if (red==1) {kc++; break;} else red++;} } } return max(max(ka,kb),kc)-min(min(ka,kb),kc); } int evalmax(int a, int b, int c) { int ka=0,kb=0,kc=0; for (auto p : perms) { int red=0; for (auto it : p) { if (it==a) {if (red==2) {ka++; break;} else red++;} if (it==b) {if (red==2) {kb++; break;} else red++;} if (it==c) {if (red==2) {kc++; break;} else red++;} } } return max(max(ka,kb),kc)-min(min(ka,kb),kc); } int evalwtf(int a, int b, int c, int d) { int ka=0,kb=0,kc=0; for (auto p : perms) { int red=0; bool svrsio=0; bool oki=false; for (auto it : p) { if (it==a) {if (oki) {ka++; svrsio=1; break;}} if (it==b) {if (oki) {kb++; svrsio=1; break;}} if (it==c) {if (oki) {kc++; svrsio=1; break;}} if (it==d) oki=true; } if (!svrsio) for (auto it : p) { if (it==a) {ka++; break;} if (it==b) {kb++; break;} if (it==c) {kc++; break;} } } return max(max(ka,kb),kc)-min(min(ka,kb),kc); } int ans[6]; void orderCoins() { if ((int)perms.size()==1) { ff(i,0,6) ans[i]=perms.back()[i]; answer(ans),init(0); return; } int koji=-1,sta=837339; vector<int> nesto; fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6) { int tval; fff(_,1,6) if (_!=i && _!=j && _!=k) { tval=evalwtf(i,j,k,_); if (tval<sta) sta=tval,koji=4,nesto={i,j,k,_}; } tval=evalmin(i,j,k); if (tval<sta) sta=tval,koji=1,nesto={i,j,k}; tval=evalmax(i,j,k); if (tval<sta) sta=tval,koji=3,nesto={i,j,k}; tval=evalmed(i,j,k); if (tval<sta) sta=tval,koji=2,nesto={i,j,k}; } vector<vector<int>> tmp; if (koji==1) { int a=nesto[0],b=nesto[1],c=nesto[2]; int x=getLightest(a,b,c); for (auto p : perms) { for (auto it : p) { if (it==a) {if (it==x) tmp.pb(p); break;} if (it==b) {if (it==x) tmp.pb(p); break;} if (it==c) {if (it==x) tmp.pb(p); break;} } } } if (koji==2) { int a=nesto[0],b=nesto[1],c=nesto[2]; int x=getMedian(a,b,c); for (auto p : perms) { int red=0; for (auto it : p) { if (it==a) {if (red==1) {if (it==x) tmp.pb(p); break;} else red++;} if (it==b) {if (red==1) {if (it==x) tmp.pb(p); break;} else red++;} if (it==c) {if (red==1) {if (it==x) tmp.pb(p); break;} else red++;} } } } if (koji==3) { int a=nesto[0],b=nesto[1],c=nesto[2]; int x=getHeaviest(a,b,c); for (auto p : perms) { int red=0; for (auto it : p) { if (it==a) {if (red==2) {if (it==x) tmp.pb(p); break;} else red++;} if (it==b) {if (red==2) {if (it==x) tmp.pb(p); break;} else red++;} if (it==c) {if (red==2) {if (it==x) tmp.pb(p); break;} else red++;} } } } if (koji==4) { int a=nesto[0],b=nesto[1],c=nesto[2],d=nesto[3]; int x=getNextLightest(a,b,c,d); for (auto p : perms) { int red=0; bool svrsio=0; bool oki=false; for (auto it : p) { if (it==a) {if (oki) {if (it==x) tmp.pb(p); svrsio=1; break;}} if (it==b) {if (oki) {if (it==x) tmp.pb(p); svrsio=1; break;}} if (it==c) {if (oki) {if (it==x) tmp.pb(p); svrsio=1; break;}} if (it==d) oki=true; } if (!svrsio) for (auto it : p) { if (it==a) {if (it==x) tmp.pb(p); break;} if (it==b) {if (it==x) tmp.pb(p); break;} if (it==c) {if (it==x) tmp.pb(p); break;} } } } perms=tmp; /*for (auto p : perms) { cout<<"jbt "; for (auto it : p) cout<<it<<" "; cout<<endl; } cout<<endl;*/ orderCoins(); } /*int main() { ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int t; cin>>t; init(t); ff(i,0,6) jp[i]=i+1; while (t--) { orderCoins(); next_permutation(jp,jp+6); } }*/

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:135:15: warning: unused parameter 'T' [-Wunused-parameter]
  135 | void init(int T)
      |           ~~~~^
scales.cpp: In function 'int evalwtf(int, int, int, int)':
scales.cpp:197:13: warning: unused variable 'red' [-Wunused-variable]
  197 |         int red=0; bool svrsio=0; bool oki=false;
      |             ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
scales.cpp:220:9: note: in expansion of macro 'ff'
  220 |         ff(i,0,6) ans[i]=perms.back()[i];
      |         ^~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:227:5: note: in expansion of macro 'fff'
  227 |     fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
      |     ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:227:16: note: in expansion of macro 'fff'
  227 |     fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
      |                ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:227:29: note: in expansion of macro 'fff'
  227 |     fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
      |                             ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of '_' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:231:9: note: in expansion of macro 'fff'
  231 |         fff(_,1,6) if (_!=i && _!=j && _!=k)
      |         ^~~
scales.cpp:298:17: warning: unused variable 'red' [-Wunused-variable]
  298 |             int red=0; bool svrsio=0; bool oki=false;
      |                 ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...