| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 984617 | jay_jayjay | Scales (IOI15_scales) | C++14 | 14 ms | 604 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.
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;
#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
#include "scales.h"
struct query {
char t, a, b, c, d;
query(){}
query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
int ex() {
int C=0;
switch(t) {
case 1: C=getHeaviest(a+1,b+1,c+1); break;
case 2: C=getLightest(a+1,b+1,c+1); break;
case 3: C=getMedian(a+1,b+1,c+1); break;
case 4: C=getNextLightest(a+1,b+1,c+1,d+1); break;
}
C--;
//printf("ex %d | %d %d %d | %d : %d\n",t,a,b,c,d,C);
return C==a?0:C==b?1:C==c?2:-1;
}
int sim(array<char,6> p) {
array<array<char,2>,3> q{ array<char,2>{p[a],a},array<char,2>{p[b],b},array<char,2>{p[c],c} };
sort(all(q));
auto [x,y,z] = q;
int C=0;
switch(t) {
case 1: C=z[1]; break;
case 2: C=x[1]; break;
case 3: C=y[1]; break;
case 4: C=p[d]<x[0]?x[1]:p[d]<y[0]?y[1]:p[d]<z[0]?z[1]:x[1]; break;
}
return C==a?0:C==b?1:C==c?2:-1;
}
bool operator < (const query& o) const { return make_tuple(t,a,b,c,d)<make_tuple(o.t,o.a,o.b,o.c,o.d); }
};
query Q[5000];
int work(int p, int T, vector<array<char,6>> z) {
if(z.size()<=1)return 0;
if(T==6)return 1;
//printf("%d %d %d\n",p,T,z.size());
//if(z.size()<10) for(auto v:z){for(auto x:v)printf("%d",x);printf("\n");}
if(T==0) {
for(auto q : {query{1,1,2,3,4},query{2,1,2,3,4},query{3,1,2,3,4},query{4,1,2,3,4}}) {
array<vector<array<char,6>>,3> np;
for(auto&x:z) np[q.sim(x)].push_back(x);
int mx = max({np[0].size(),np[1].size(),np[2].size()});
if(mx>240)continue;
if(work(3*p+1,T+1, np[0])) continue;
if(work(3*p+2,T+1, np[1])) continue;
if(work(3*p+3,T+1, np[2])) continue;
Q[p]=q;
return 0;
}
return 1;
}
for(int t=1;t<5;t++) {
for(int d=0;d<(t==4?6:1);d++) {
for(int a=0;a<6;a++)
for(int b=a+1;b<6;b++)
for(int c=b+1;c<6;c++) {
if(t==4 && (a==d||b==d||c==d)) continue;
query q{t,a,b,c,d};
array<vector<array<char,6>>,3> np;
for(auto&x:z) np[q.sim(x)].push_back(x);
int mx = max({np[0].size(),np[1].size(),np[2].size()});
if(T==1&&mx>80)continue;
if(T==2&&mx>27)continue;
if(T==3&&mx>9)continue;
if(T==4&&mx>3)continue;
if(T==5&&mx>1)continue;
if(work(3*p+1,T+1, np[0])) continue;
if(work(3*p+2,T+1, np[1])) continue;
if(work(3*p+3,T+1, np[2])) continue;
Q[p]=q;
return 0;
}
}
}
return 1;
}
void init(int T) {
if(query(1,1,2,3,4).sim({1,2,3,4,5,6}) != 2)assert(0);
if(query(2,1,2,3,4).sim({1,2,3,4,5,6}) != 0)assert(0);
if(query(3,1,2,3,4).sim({1,2,3,4,5,6}) != 1)assert(0);
if(query(3,1,3,4,2).sim({1,2,3,4,5,6}) != 1)assert(0);
vector<array<char,6>> v;
array<char,6> a{1,2,3,4,5,6};
do { v.push_back(a); } while(next_permutation(all(a)));
int st = work(0, 0, v);
//printf("%d\n",st);
}
void orderCoins() {
vector<array<char,6>> v;
array<char,6> a{1,2,3,4,5,6};
do { v.push_back(a); } while(next_permutation(all(a)));
int i=0;
while(v.size()>1) {
//printf("%d %d\n",i, v.size());
query q = Q[i];
int s;
i = i*3 + (s=q.ex())+1;
decltype(v) nv;
for(auto p:v)if(q.sim(p)==s)nv.push_back(p);
v=nv;
}
//printf("%d %d\n",i, v.size());
auto p=v[0];
int W[6];
for(int i=0;i<6;i++)W[+p[i]-1] = i+1;
answer(W);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||