| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 239655 | tduong0806 | Scales (IOI15_scales) | C++14 | 1097 ms | 2688 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>
#include "scales.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int hmt() {int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';if(n) x=-x;return x;}
#define in hmt()
#define ins ({string x;char c=getchar();for(;c==' '||c=='\n';c=getchar());for(;c!=' '&&c!='\n';c=getchar()) x+=c;x;})
#define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forb(i,BS) for(int i=BS._Find_first();i< BS.size();i = BS._Find_next(i))
#define timer 1.0*clock()/CLOCKS_PER_SEC
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
const int N=7,M=800;
int a[N],p[M][N],kt[M][M],res;
struct oo
{
int it,A,B,C,D,E;
} q[M];
/*map<vector<int>,int> f;
int F(vector<int> a,int l)
{
if(a.size()==1) return 0;
if(l>=6) return 10;
if(f[a]) return f[a];
int ret=10;
forinc(i,1,360) if(i%3==1)
{
int mx=-1;
forinc(j,0,2)
{
vector<int> b;
forv(e,a) if(kt[e][i+j]) b.pb(e);
if(b.size()&&b.size()<a.size()) mx=max(mx,F(b,l+1));
}
if(mx!=-1) ret=min(ret,mx+1);
if(ret+l==6) break;
}
//cout<<a.size()<<" "<<ret<<"\n";
/*cout<<"test\n";
cout<<a.size()<<"\n";
forv(x,a) {cout<<x<<" ";cout<<"\n";}
cout<<ret<<"\n";exit(0);
return f[a]=ret;
}*/
void init(int T)
{
forinc(i,1,6) a[i]=i;
int cnt=0;
do
{
++cnt;
forinc(i,1,6) p[cnt][a[i]]=i;
}
while(next_permutation(a+1,a+7));
cnt=0;
forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
{
forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={1,A,B,C,0,i};
forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={2,A,B,C,0,i};
forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={3,A,B,C,0,i};
}
forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
if(A!=D&&B!=D&&C!=D) forinc(i,1,3) if(A==i||B==i||C==i) q[++cnt]={4,A,B,C,D,i};
forinc(i,1,720) forinc(j,1,360)
{
int it=q[j].it,A=q[j].A,B=q[j].B,C=q[j].C,D=q[j].D,E=q[j].E;
int ma=max({p[i][A],p[i][B],p[i][C]});
int mi=min({p[i][A],p[i][B],p[i][C]});
if(it==1) kt[i][j]=(p[i][E]>=ma);
else if(it==2) kt[i][j]=(p[i][E]<=mi);
else if(it==3) kt[i][j]=(p[i][E]>mi&&p[i][E]<ma);
else if(it==4)
{
if(p[i][D]>ma) kt[i][j]=(p[i][E]<=mi);
else
{
bool ok=1;
if(p[i][D]>p[i][E]) ok=0;
else
{
if(p[i][A]>p[i][D]&&p[i][A]<p[i][E]) ok=0;
if(p[i][B]>p[i][D]&&p[i][B]<p[i][E]) ok=0;
if(p[i][C]>p[i][D]&&p[i][C]<p[i][E]) ok=0;
}
kt[i][j]=ok;
}
}
}
}
void orderCoins()
{
vector<int> a;
forinc(i,1,720) a.pb(i);
while(a.size()>1)
{
int ret=1000,j;
forinc(i,1,360) if(i%3==1)
{
int mx=-1;
forinc(j,0,2)
{
vector<int> b;
forv(e,a) if(kt[e][i+j]) b.pb(e);
if(b.size()&&b.size()<a.size()) mx=max(mx,int(b.size()));
}
if(mx!=-1&&ret>mx+1) ret=mx+1,j=i;
}
int it=q[j].it,A=q[j].A,B=q[j].B,C=q[j].C,D=q[j].D,E;
if(it==1) E=getHeaviest(A,B,C);
else if(it==2) E=getLightest(A,B,C);
else if(it==3) E=getMedian(A,B,C);
else if(it==4) E=getNextLightest(A,B,C,D);
forinc(i,1,360) if(i==j)
{
forinc(j,0,2) if(q[i+j].E==E)
{
vector<int> b;
forv(e,a) if(kt[e][i+j]) b.pb(e);
a=b;
}
}
}
int ans[6];
forinc(i,1,6) ans[p[a[0]][i]-1]=i;
answer(ans);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||