| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 379290 |
2021-03-17T20:45:53 Z |
IloveN |
Scales (IOI15_scales) |
C++14 |
|
493 ms |
4952 KB |
#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e3+10,max_depth=6;
struct query
{
int tp,a,b,c,d;
};
vi permu[N];
query Q[N];
int q=0,pos[N],pw3[N];
int heavy(int a,int b,int c)
{
if (pos[b]>pos[a]) swap(a,b);
if (pos[c]>pos[a]) return c;
return a;
}
int light(int a,int b,int c)
{
if (pos[b]<pos[a]) swap(a,b);
if (pos[c]<pos[a]) return c;
return a;
}
int med(int a,int b,int c)
{
if (pos[b]>pos[a]) swap(a,b);
if (pos[c]>pos[a]) swap(a,c);
if (pos[b]>pos[c]) return b;
return c;
}
int next_light(int a,int b,int c,int d)
{
int mn=10,res;
if (pos[a]>pos[d] && pos[a]<mn) mn=pos[a],res=a;
if (pos[b]>pos[d] && pos[b]<mn) mn=pos[b],res=b;
if (pos[c]>pos[d] && pos[c]<mn) mn=pos[c],res=c;
if (mn!=10) return res;
return light(a,b,c);
}
int ans[N][N];
map<vi,int> choose;
bool solve(vi &vt,int depth)
{
if ((int)vt.size()>pw3[depth]) return false;
if ((int)vt.size()<=1) return true;
if (depth==max_depth)
{
vi cq={1,21,41,61};
for (int i : cq)
{
vi nxvt[7];
for (int x : vt) nxvt[ans[x][i]].eb(x);
int check=1;
for (int j=1;j<=6;j++)
if (!nxvt[j].empty())
{
if (!solve(nxvt[j],depth-1))
{
check=0;
break;
}
}
if (check)
{
choose[vt]=i;
return true;
}
}
return false;
}
for (int i=1;i<=q;i++)
{
vi nxvt[7];
for (int x : vt) nxvt[ans[x][i]].eb(x);
int check=1;
for (int j=1;j<=6;j++)
if (!nxvt[j].empty())
{
if (!solve(nxvt[j],depth-1))
{
check=0;
break;
}
}
if (check)
{
choose[vt]=i;
return true;
}
}
return false;
}
void precal()
{
vi vt;
for (int i=1;i<=6;i++) vt.eb(i);
for (int i=1;i<=720;i++)
{
permu[i]=vt;
next_permutation(all(vt));
}
for (int tp=1;tp<=3;tp++)
for (int a=1;a<=6;a++)
for (int b=a+1;b<=6;b++)
for (int c=b+1;c<=6;c++) Q[++q]={tp,a,b,c,0};
for (int a=1;a<=6;a++)
for (int b=a+1;b<=6;b++)
for (int c=b+1;c<=6;c++)
for (int d=1;d<=6;d++)
if (d!=a && d!=b && d!=c) Q[++q]={4,a,b,c,d};
for (int i=1;i<=720;i++)
{
for (int j=0;j<6;j++) pos[permu[i][j]]=j;
for (int j=1;j<=q;j++)
{
int tp=Q[j].tp,a=Q[j].a,b=Q[j].b,c=Q[j].c,d=Q[j].d;
if (tp==1) ans[i][j]=heavy(a,b,c);
else if (tp==2) ans[i][j]=light(a,b,c);
else if (tp==3) ans[i][j]=med(a,b,c);
else ans[i][j]=next_light(a,b,c,d);
}
}
pw3[0]=1;
for (int i=1;i<=max_depth;i++) pw3[i]=pw3[i-1]*3;
vt.clear();
for (int i=1;i<=720;i++) vt.eb(i);
solve(vt,max_depth);
}
int ask(int id)
{
int tp=Q[id].tp,a=Q[id].a,b=Q[id].b,c=Q[id].c,d=Q[id].d;
if (tp==1) return getHeaviest(a,b,c);
if (tp==2) return getLightest(a,b,c);
if (tp==3) return getMedian(a,b,c);
return getNextLightest(a,b,c,d);
}
void init(int T)
{
precal();
}
void orderCoins()
{
vi vt;
for (int i=1;i<=720;i++) vt.eb(i);
while (vt.size()>1)
{
int id=choose[vt];
int d=ask(id);
vi vt2;
for (int x : vt)
if (ans[x][id]==d) vt2.eb(x);
vt=vt2;
}
int W[6];
for (int i=0;i<6;i++) W[i]=permu[vt[0]][i];
answer(W);
}
/*int main()
{
//freopen("ss.inp","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
precal();
return 0;
}*/
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:159:15: warning: unused parameter 'T' [-Wunused-parameter]
159 | void init(int T)
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
452 ms |
4720 KB |
Output is correct |
| 2 |
Correct |
465 ms |
4716 KB |
Output is correct |
| 3 |
Correct |
487 ms |
4952 KB |
Output is correct |
| 4 |
Correct |
458 ms |
4716 KB |
Output is correct |
| 5 |
Correct |
465 ms |
4716 KB |
Output is correct |
| 6 |
Correct |
477 ms |
4716 KB |
Output is correct |
| 7 |
Correct |
449 ms |
4844 KB |
Output is correct |
| 8 |
Correct |
453 ms |
4716 KB |
Output is correct |
| 9 |
Correct |
455 ms |
4716 KB |
Output is correct |
| 10 |
Correct |
465 ms |
4716 KB |
Output is correct |
| 11 |
Correct |
451 ms |
4716 KB |
Output is correct |
| 12 |
Correct |
450 ms |
4844 KB |
Output is correct |
| 13 |
Correct |
452 ms |
4716 KB |
Output is correct |
| 14 |
Correct |
493 ms |
4716 KB |
Output is correct |
| 15 |
Correct |
454 ms |
4716 KB |
Output is correct |
| 16 |
Correct |
456 ms |
4844 KB |
Output is correct |
| 17 |
Correct |
458 ms |
4844 KB |
Output is correct |
| 18 |
Correct |
451 ms |
4716 KB |
Output is correct |
| 19 |
Correct |
452 ms |
4716 KB |
Output is correct |
| 20 |
Correct |
473 ms |
4716 KB |
Output is correct |
| 21 |
Correct |
471 ms |
4852 KB |
Output is correct |
| 22 |
Correct |
457 ms |
4716 KB |
Output is correct |
| 23 |
Correct |
448 ms |
4716 KB |
Output is correct |
| 24 |
Correct |
454 ms |
4664 KB |
Output is correct |
| 25 |
Correct |
454 ms |
4664 KB |
Output is correct |
| 26 |
Correct |
461 ms |
4716 KB |
Output is correct |
| 27 |
Correct |
454 ms |
4716 KB |
Output is correct |
| 28 |
Correct |
457 ms |
4716 KB |
Output is correct |
| 29 |
Correct |
452 ms |
4708 KB |
Output is correct |
| 30 |
Correct |
469 ms |
4716 KB |
Output is correct |
| 31 |
Correct |
450 ms |
4716 KB |
Output is correct |
| 32 |
Correct |
454 ms |
4832 KB |
Output is correct |
| 33 |
Correct |
450 ms |
4844 KB |
Output is correct |
| 34 |
Correct |
454 ms |
4844 KB |
Output is correct |
| 35 |
Correct |
459 ms |
4916 KB |
Output is correct |
| 36 |
Correct |
457 ms |
4668 KB |
Output is correct |
| 37 |
Correct |
451 ms |
4716 KB |
Output is correct |
| 38 |
Correct |
456 ms |
4792 KB |
Output is correct |
| 39 |
Correct |
455 ms |
4716 KB |
Output is correct |
| 40 |
Correct |
452 ms |
4716 KB |
Output is correct |
