| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 239656 | tduong0806 | 저울 (IOI15_scales) | C++14 | 73 ms | 2816 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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,6) 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;
}
}
}
}
/*int getHeaviest(int A,int B,int C)
{
cout<<"getHeaviest"<<" "<<A<<" "<<B<<" "<<C<<"\n";
int x;cin>>x;
return x;
}
int getMedian(int A,int B,int C)
{
cout<<"getMedian"<<" "<<A<<" "<<B<<" "<<C<<"\n";
int x;cin>>x;
return x;
}
int getLightest(int A,int B,int C)
{
cout<<"getLightest"<<" "<<A<<" "<<B<<" "<<C<<"\n";
int x;cin>>x;
return x;
}
int getNextLightest(int A,int B,int C,int D)
{
cout<<"getNextLightest"<<" "<<A<<" "<<B<<" "<<C<<" "<<D<<"\n";
int x;cin>>x;
return x;
}
void answer(int a[])
{
cout<<"answer\n";
forinc(i,0,5) cout<<a[i]<<" ";
}*/
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);
}
/*int main()
{
init(0);
orderCoins();
}*/
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||