| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 678917 | n0sk1ll | Scales (IOI15_scales) | C++14 | 386 ms | 237024 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
#include "scales.h"
vector<vector<int>> perms;
mt19937 rng(29042004);
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 idx=1;
int g[10000007][3];
vector<int> stapitam[10000007]; //ne pitam nista ako znam odgovor
bool generate_tree(int p, vector<vector<int>> sperms, int d)
{
//cout<<p<<" "<<sperms.size()<<" "<<d<<endl;
if (d>=7) return false;
if (sperms.size()==1)
{
stapitam[p]=sperms.back();
return true;
}
if (sperms.empty()) return true;
perms=sperms;
vector<vector<int>> qrys;
int sta=837339;
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) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({4,i,j,k,_});
}
tval=evalmed(i,j,k);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({2,i,j,k});
tval=evalmin(i,j,k);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({1,i,j,k});
tval=evalmax(i,j,k);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({3,i,j,k});
}
shuffle(all(qrys),rng);
int upito=0;
for (auto qq : qrys)
{
if (upito>sperms.size()/80+5) return false;
upito++;
stapitam[p]=qq;
vector<vector<int>> gde1,gde2,gde3;
if (qq[0]==1)
{
int a=qq[1],b=qq[2],c=qq[3];
for (auto p : sperms)
{
for (auto it : p)
{
if (it==a) {gde1.pb(p); break;}
if (it==b) {gde2.pb(p); break;}
if (it==c) {gde3.pb(p); break;}
}
}
}
if (qq[0]==2)
{
int a=qq[1],b=qq[2],c=qq[3];
for (auto p : sperms)
{
int red=0;
for (auto it : p)
{
if (it==a) {if (red==1) {gde1.pb(p); break;} else red++;}
if (it==b) {if (red==1) {gde2.pb(p); break;} else red++;}
if (it==c) {if (red==1) {gde3.pb(p); break;} else red++;}
}
}
}
if (qq[0]==3)
{
int a=qq[1],b=qq[2],c=qq[3];
for (auto p : sperms)
{
int red=0;
for (auto it : p)
{
if (it==a) {if (red==2) {gde1.pb(p); break;} else red++;}
if (it==b) {if (red==2) {gde2.pb(p); break;} else red++;}
if (it==c) {if (red==2) {gde3.pb(p); break;} else red++;}
}
}
}
if (qq[0]==4)
{
int a=qq[1],b=qq[2],c=qq[3],d=qq[4];
for (auto p : sperms)
{
int red=0; bool svrsio=0; bool oki=false;
for (auto it : p)
{
if (it==a) {if (oki) {gde1.pb(p); svrsio=1; break;}}
if (it==b) {if (oki) {gde2.pb(p); svrsio=1; break;}}
if (it==c) {if (oki) {gde3.pb(p); svrsio=1; break;}}
if (it==d) oki=true;
}
if (!svrsio) for (auto it : p)
{
if (it==a) {gde1.pb(p); break;}
if (it==b) {gde2.pb(p); break;}
if (it==c) {gde3.pb(p); break;}
}
}
}
//cout<<qq[0]<<" ? "<<gde1.size()<<" "<<gde2.size()<<" "<<gde3.size()<<endl;
bool ok=true;
g[p][0]=++idx;
g[p][1]=++idx;
g[p][2]=++idx;
if (!generate_tree(g[p][0],gde1,d+1)) ok=false;
if (!generate_tree(g[p][1],gde2,d+1)) ok=false;
if (!generate_tree(g[p][2],gde3,d+1)) ok=false;
if (ok) return true;
}
return false;
}
void init(int T)
{
vector<int> tperm={1,2,3,4,5,6};
do
{
perms.pb(tperm);
} while (next_permutation(all(tperm)));
assert(generate_tree(1,perms,0));
}
int ans[6];
void dfs(int p)
{
if (stapitam[p].size()==6)
{
ff(i,0,6) ans[i]=stapitam[p][i];
answer(ans);
}
else if (stapitam[p].front()==1)
{
int x=getLightest(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
else if (stapitam[p].front()==2)
{
int x=getMedian(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
else if (stapitam[p].front()==3)
{
int x=getHeaviest(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
else
{
int x=getNextLightest(stapitam[p][1],stapitam[p][2],stapitam[p][3],stapitam[p][4]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
}
void orderCoins()
{
dfs(1);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||