Submission #1188797

#TimeUsernameProblemLanguageResultExecution timeMemory
1188797simona1230Scales (IOI15_scales)C++20
100 / 100
11 ms644 KiB
#include "scales.h" //#include "graderlib.c" #include <bits/stdc++.h> using namespace std; int id,p[1024][32],h[32],in[32]; void perm(int i) { if(i==7) { id++; for(int j=1; j<=6; j++) p[id][h[j]]=j; return; } for(int j=1; j<=6; j++) { if(in[j])continue; in[j]=1; h[i]=j; perm(i+1); in[j]=0; } } map<vector<int>, int> mp; bool build(vector<int> v,int cnt) { if(mp[v]!=0) { if(mp[v]==-1)return 0; return 1; } if(v.size()<=1)return 1; for(int i1=1; i1<=4; i1++) { for(int i2=i1+1; i2<=5; i2++) { for(int i3=i2+1; i3<=6; i3++) { for(int t=0; t<=2; t++) { vector<int> v1= {},v2= {},v3= {}; for(int i=0; i<v.size(); i++) { int j=v[i]; if(t==0) { if(p[j][i1]<p[j][i2]&&p[j][i1]<p[j][i3])v1.push_back(j); else if(p[j][i2]<p[j][i1]&&p[j][i2]<p[j][i3])v2.push_back(j); else v3.push_back(j); } if(t==1) { if(p[j][i1]>p[j][i2]&&p[j][i1]<p[j][i3])v1.push_back(j); else if(p[j][i1]>p[j][i3]&&p[j][i1]<p[j][i2])v1.push_back(j); else if(p[j][i2]>p[j][i1]&&p[j][i2]<p[j][i3])v2.push_back(j); else if(p[j][i2]>p[j][i3]&&p[j][i2]<p[j][i1])v2.push_back(j); else v3.push_back(j); } if(t==2) { if(p[j][i1]>p[j][i2]&&p[j][i1]>p[j][i3])v1.push_back(j); else if(p[j][i2]>p[j][i1]&&p[j][i2]>p[j][i3])v2.push_back(j); else v3.push_back(j); } } if(v1.size()<=cnt/3&&v2.size()<=cnt/3&&v3.size()<=cnt/3&&build(v1,cnt/3)&&build(v2,cnt/3)&&build(v3,cnt/3)) { mp[v]=i1*1000+i2*100+i3*10+t; return 1; } } for(int i4=1; i4<=6; i4++) { if(i1==i4||i2==i4||i3==i4)continue; vector<int> v1= {},v2= {},v3= {}; for(int i=0; i<v.size(); i++) { int j=v[i]; int h1=7,h2=7,h3=7; if(p[j][i1]>p[j][i4])h1=p[j][i1]; if(p[j][i2]>p[j][i4])h2=p[j][i2]; if(p[j][i3]>p[j][i4])h3=p[j][i3]; if(h1+h2+h3==21) { if(p[j][i1]<p[j][i2]&&p[j][i1]<p[j][i3])v1.push_back(j); else if(p[j][i2]<p[j][i1]&&p[j][i2]<p[j][i3])v2.push_back(j); else v3.push_back(j); } else { int mn=min(h1,min(h2,h3)); if(mn==h1)v1.push_back(j); else if(mn==h2)v2.push_back(j); else v3.push_back(j); } } if(v1.size()<=cnt/3&&v2.size()<=cnt/3&&v3.size()<=cnt/3&&build(v1,cnt/3)&&build(v2,cnt/3)&&build(v3,cnt/3)) { mp[v]=i4*10000+i1*1000+i2*100+i3*10+3; return 1; } } } } } mp[v]=-1; return 0; } void init(int T) {} int ans[6]; void orderCoins() { id=0; perm(1); vector<int> v; for(int i=1; i<=id; i++) v.push_back(i); build(v,729); //cout<<mp[v]<<endl; while(v.size()>1) { int i1=mp[v]/1000%10; int i2=mp[v]/100%10; int i3=mp[v]/10%10; int i4=mp[v]/10000; int t=mp[v]%10; vector<int> v1= {},v2= {},v3= {}; for(int i=0; i<v.size(); i++) { int j=v[i]; if(t==0) { if(p[j][i1]<p[j][i2]&&p[j][i1]<p[j][i3])v1.push_back(j); else if(p[j][i2]<p[j][i1]&&p[j][i2]<p[j][i3])v2.push_back(j); else v3.push_back(j); } else if(t==1) { if(p[j][i1]>p[j][i2]&&p[j][i1]<p[j][i3])v1.push_back(j); else if(p[j][i1]>p[j][i3]&&p[j][i1]<p[j][i2])v1.push_back(j); else if(p[j][i2]>p[j][i1]&&p[j][i2]<p[j][i3])v2.push_back(j); else if(p[j][i2]>p[j][i3]&&p[j][i2]<p[j][i1])v2.push_back(j); else v3.push_back(j); } else if(t==2) { if(p[j][i1]>p[j][i2]&&p[j][i1]>p[j][i3])v1.push_back(j); else if(p[j][i2]>p[j][i1]&&p[j][i2]>p[j][i3])v2.push_back(j); else v3.push_back(j); } else { int h1=7,h2=7,h3=7; if(p[j][i1]>p[j][i4])h1=p[j][i1]; if(p[j][i2]>p[j][i4])h2=p[j][i2]; if(p[j][i3]>p[j][i4])h3=p[j][i3]; if(h1+h2+h3==21) { if(p[j][i1]<p[j][i2]&&p[j][i1]<p[j][i3])v1.push_back(j); else if(p[j][i2]<p[j][i1]&&p[j][i2]<p[j][i3])v2.push_back(j); else v3.push_back(j); } else { int mn=min(h1,min(h2,h3)); if(mn==h1)v1.push_back(j); else if(mn==h2)v2.push_back(j); else v3.push_back(j); } } } int x; if(t==0)x=getLightest(i1,i2,i3); else if(t==1)x=getMedian(i1,i2,i3); else if(t==2)x=getHeaviest(i1,i2,i3); else x=getNextLightest(i1,i2,i3,i4); if(x==i1)v=v1; else if(x==i2)v=v2; else v=v3; } for(int i=1;i<=6;i++) ans[p[v[0]][i]-1]=i; answer(ans); } /* int main() { orderCoins(); return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...