| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 130335 | hamzqq9 | Scales (IOI15_scales) | C++14 | 152 ms | 1792 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 "scales.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007
#define M 20000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;
struct query {
int t;
vector<int> inds;
};
struct node {
vector<int> ch;
query ask;
} T[10000];
int root,tot;
int perm[10000];
vector<vector<int>> ps;
int req[]={243,81,27,9,3,1};
vector<query> qs;
int Light(int who,query ask) {
if(ps[who][ask.inds[0]]<ps[who][ask.inds[1]] && ps[who][ask.inds[0]]<ps[who][ask.inds[2]]) return 0;
if(ps[who][ask.inds[1]]<ps[who][ask.inds[0]] && ps[who][ask.inds[1]]<ps[who][ask.inds[2]]) return 1;
return 2;
}
int Heavy(int who,query ask) {
if(ps[who][ask.inds[0]]>ps[who][ask.inds[1]] && ps[who][ask.inds[0]]>ps[who][ask.inds[2]]) return 0;
if(ps[who][ask.inds[1]]>ps[who][ask.inds[0]] && ps[who][ask.inds[1]]>ps[who][ask.inds[2]]) return 1;
return 2;
}
int Median(int who,query ask) {
int ok[3]={0};
ok[Light(who,ask)]=1;
ok[Heavy(who,ask)]=1;
for(int i=0;i<3;i++) {
if(!ok[i]) return i;
}
}
int Next(int who,query ask) {
int lg;
int md;
int hv;
if(ps[who][ask.inds[3]]<ps[who][ask.inds[lg=Light(who,ask)]]) return lg;
if(ps[who][ask.inds[3]]<ps[who][ask.inds[md=Median(who,ask)]]) return md;
if(ps[who][ask.inds[3]]<ps[who][ask.inds[hv=Heavy(who,ask)]]) return hv;
return lg;
}
int eval(int who,query ask) {
if(ask.t==0) return Heavy(who,ask);
if(ask.t==1) return Light(who,ask);
if(ask.t==2) return Median(who,ask);
return Next(who,ask);
}
vector<int> get(int root) {
if(T[root].ch.empty()) return ps[perm[root]];
int id;
int t=T[root].ask.t;
vector<int> inds=T[root].ask.inds;
if(t==0) id=getHeaviest(inds[0]+1,inds[1]+1,inds[2]+1);
if(t==1) id=getLightest(inds[0]+1,inds[1]+1,inds[2]+1);
if(t==2) id=getMedian(inds[0]+1,inds[1]+1,inds[2]+1);
if(t==3) id=getNextLightest(inds[0]+1,inds[1]+1,inds[2]+1,inds[3]+1);
for(int i=0;i<sz(inds);i++) {
if(inds[i]==id-1) {
return get(T[root].ch[i]);
}
}
assert(0);
}
int mxh;
int build(vector<int> ind,int h) {
umax(mxh,h);
if(sz(ind)<=1) {
++tot;
if(sz(ind)) perm[tot]=ind[0];
return tot;
}
for(int i=0;i<sz(qs);i++) {
query ask=qs[i];
vector<int> branch[3];
for(auto cur:ind) {
int res=eval(cur,ask);
branch[res].pb(cur);
}
bool flag=1;
for(int j=0;j<3;j++) {
flag&=(sz(branch[j])<=req[h]);
}
if(!flag) continue ;
int bef=tot;
vector<int> roots;
for(int j=0;j<3 && flag;j++) {
roots.pb(build(branch[j],h+1));
flag&=(roots.back()!=-1);
}
if(!flag) {
tot=bef;
continue ;
}
T[++tot]={roots,ask};
return tot;
}
return -1;
}
void init(int T) {
srand(time(NULL));
vector<int> p;
vector<int> ind;
for(int i=1;i<=6;i++) p.pb(i);
do {
ps.pb(p);
} while(next_permutation(all(p)));
for(int i=0;i<720;i++) ind.pb(i);
for(int i=0;i<6;i++) {
for(int j=i+1;j<6;j++) {
for(int k=j+1;k<6;k++) {
for(int t=0;t<3;t++) {
qs.pb({t,{i,j,k}});
}
for(int l=0;l<6;l++) {
qs.pb({3,{i,j,k,l}});
}
}
}
}
random_shuffle(all(qs));
root=build(ind,0);
}
void orderCoins() {
int W[6];
vector<int> res=get(root);
for(int i=0;i<6;i++) W[res[i]-1]=i+1;
answer(W);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||