| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1028565 | pcc | Scales (IOI15_scales) | C++17 | 427 ms | 51552 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>
using namespace std;
#define tiii tuple<int,int,int>
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6+10;
const int N = 6;
int tp[mxn];
vector<pii> tree[mxn];
int pw[N+1];
int ep = 0;
const int lim = 10000;
vector<int> param[mxn];
int encode(vector<int> v){
assert(v.size() == N);
int re = 0;
for(int i = 0;i<v.size();i++){
re += v[i]*pw[i];
}
return re;
}
vector<int> decode(int k){
vector<int> re(N);
for(int i = 0;i<N;i++){
re[i] = k%N;
k/=N;
}
return re;
}
namespace TREE{
vector<int> cases;
vector<int> op;
bitset<mxn> done;
void init(){
int pt = 0;
for(int i = 0;i<N;i++){
for(int j = i+1;j<N;j++){
for(int k = j+1;k<N;k++){
param[pt] = {i,j,k,1};
op.push_back(pt);
pt++;
param[pt] = {i,j,k,2};
op.push_back(pt);
pt++;
param[pt] = {i,j,k,3};
op.push_back(pt);
pt++;
for(int l = 0;l<N;l++){
if(l == i||l == j||l == k)continue;
param[pt] = {i,j,k,l,4};
op.push_back(pt);
pt++;
}
}
}
}
//cerr<<"OPS: "<<op.size()<<endl;
vector<int> perm(N);for(int i = 0;i<N;i++)perm[i] = i;
do{
cases.push_back(encode(perm));
}while(next_permutation(perm.begin(),perm.end()));
//cerr<<"CASES: "<<cases.size()<<endl;
return;
}
int f(int opid,int val,bool p = false){
auto v = param[opid];
auto arr = decode(val);
sort(v.begin(),v.begin()+3,[&](int a,int b){return arr[a]<arr[b];});
assert(arr[v[1]]>arr[v[0]]&&arr[v[2]]>arr[v[1]]);
int re = -1;
if(v.back() == 1)re = v[2];
else if(v.back() == 2)re = v[0];
else if(v.back() == 3)re = v[1];
else{
for(int i = 0;i<3;i++){
if(arr[v[i]]>arr[v[3]]){
re = v[i];
break;
}
if(i == 2)re = v[0];
}
}
if(p){
cerr<<"F: ";for(auto &i:arr)cerr<<i<<' ';cerr<<"::"<<endl;
for(auto &i:v)cerr<<i<<',';cerr<<endl;
cerr<<re<<endl;
}
return re;
}
vector<pair<int,vector<int>>> part(int opid,vector<int> &v){
vector<pair<int,vector<int>>> re;
for(int i = 0;i<v.size();i++){
int val = f(opid,v[i]);
bool gp = false;
for(auto &j:re){
if(j.fs == val)gp = true,j.sc.push_back(v[i]);
}
if(!gp)re.push_back(make_pair(val,vector<int>(1,v[i])));
}
return re;
}
int vcnt = 0;
int newnode(){
tree[vcnt].clear();
return vcnt++;
}
bool dfs(vector<int> &v,int dep,int nodeid){//false if fails
if(v.size() == 1){
tp[nodeid] = v[0];
return true;
}
if(dep>=8)return false;
ep++;
//if(ep%lim == 0)cout<<ep<<" tries"<<','<<nodeid<<endl;
//cerr<<nodeid<<":"<<dep<<','<<v.size()<<endl;
for(auto &opid:op){
if(done[opid])continue;
auto arr = part(opid,v);
assert(arr.size()<=3);
int sum = 0;
bool flag = true;
for(auto &i:arr)sum += i.sc.size();
for(auto &i:arr){
if(sum>10&&sum-i.sc.size()<=5)flag = false;
if(sum == i.sc.size())flag = false;
}
if(!flag)continue;
done[opid] = true;
tp[nodeid] = opid;
for(auto &i:arr){
tree[nodeid].push_back(pii(i.fs,newnode()));
flag = flag&&dfs(i.sc,dep+1,tree[nodeid].back().sc);
if(!flag)break;
}
done[opid] = false;
if(flag)return true;
tp[nodeid] = -1;
while(vcnt>nodeid){
vcnt--;
tp[vcnt] = -1;
tree[vcnt].clear();
}
assert(nodeid == newnode());
}
return false;
}
void GO(){
init();
int s = clock();
srand(7122);
random_shuffle(op.begin()+1,op.end());
dfs(cases,0,newnode());
cerr<<(clock()-s)/(float)CLOCKS_PER_SEC<<"seconds"<<endl;
cerr<<"TREE DONE!: "<<vcnt<<endl;
/*
cout<<"vector<int> tp = {";
for(int i = 0;i<vcnt;i++)cout<<tp[i]<<",}"[i==vcnt-1];cout<<";"<<endl;
cout<<"stringstream ss(";
for(int i = 0;i<vcnt;i++){
for(auto nxt:tree[i])cout<<i<<' '<<nxt.fs<<' '<<nxt.sc<<endl;
if(tree[i].empty()){
auto arr = decode(tp[i]);
//cerr<<i<<": ";for(auto &i:arr)cerr<<i<<' ';cerr<<endl;
}
}
cout<<");";
*/
return;
}
}
void init(int T) {
memset(tp,-1,sizeof(tp));
pw[0] = 1;
for(int i = 1;i<=N;i++)pw[i] = pw[i-1]*N;
TREE::GO();
}
int ask(int opid){
assert(opid>=0);
auto v = param[opid];
cerr<<"ASK: ";for(auto &i:v)cerr<<i<<':';
if(v.back() == 1)return getHeaviest(v[0]+1,v[1]+1,v[2]+1)-1;
else if(v.back() == 2)return getLightest(v[0]+1,v[1]+1,v[2]+1)-1;
else if(v.back() == 3)return getMedian(v[0]+1,v[1]+1,v[2]+1)-1;
else return getNextLightest(v[0]+1,v[1]+1,v[2]+1,v[3]+1)-1;
}
void orderCoins() {
/* ... */
int now = 0;
while(!tree[now].empty()){
cerr<<tp[now]<<"::";
int tmp = ask(tp[now]);
cerr<<":::"<<tmp<<endl;
for(auto &j:tree[now]){
if(j.fs == tmp){
now = j.sc;
break;
}
}
}
cerr<<"f(0,tp[now]): "<<TREE::f(0,tp[now],true)<<endl;
auto tmp = decode(tp[now]);
cerr<<"TMP: ";for(auto &i:tmp)cerr<<i<<' ';cerr<<endl;
auto ans = tmp;
for(int i = 0;i<N;i++)ans[tmp[i]] = i;
cerr<<"ANSWEr: ";for(auto &i:ans)cerr<<i<<' ';cerr<<endl;
int re[N];
for(int i = 0;i<N;i++)re[i] = ans[i]+1;
answer(re);
return;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||