| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 678876 | n0sk1ll | Scales (IOI15_scales) | C++14 | 6 ms | 364 KiB |
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>
#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 getLightest(int a, int b, int c)
{
cout<<"lightest "<<a<<" "<<b<<" "<<c<<endl;
int x; cin>>x; return x;
}
int getMedian(int a, int b, int c)
{
cout<<"median "<<a<<" "<<b<<" "<<c<<endl;
int x; cin>>x; return x;
}
int getHeaviest(int a, int b, int c)
{
cout<<"heaviest "<<a<<" "<<b<<" "<<c<<endl;
int x; cin>>x; return x;
}
int getNextLightest(int a, int b, int c, int d)
{
cout<<"wtf query "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
int x; cin>>x; return x;
}
void answer(int* sta)
{
ff(i,0,6) cout<<sta[i]<<" ";
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;
for (auto it : p)
{
bool oki;
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);
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=evalmin(i,j,k);
if (tval<sta) sta=tval,koji=1,nesto={i,j,k};
tval=evalmed(i,j,k);
if (tval<sta) sta=tval,koji=2,nesto={i,j,k};
tval=evalmax(i,j,k);
if (tval<sta) sta=tval,koji=3,nesto={i,j,k};
ff(_,0,6) if (_!=i && _!=j && _!=k)
{
tval=evalwtf(i,j,k,_);
if (tval<sta) sta=tval,koji=4,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;
for (auto it : p)
{
bool oki;
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;
orderCoins();
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
init(1);
orderCoins();
}
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||