| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 73501 | MKopchev | 저울 (IOI15_scales) | C++14 | 141 ms | 1132 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
vector< vector<int> > active;
vector<int> all;
map< vector< vector<int> >,bool > seen[15];
int maxi(int a,int b,int c)
{
return max(max(a,b),c);
}
int mini(int a,int b,int c)
{
return min(min(a,b),c);
}
int lim[10]={1,3,9,27,81,243,729,2187,6561};
bool can(int tests,vector< vector<int> > &now)
{
//cout<<tests<<" "<<now.size()<<endl;
if(now.size()<=1)return 1;
if(lim[tests]<now.size())return 0;
if(seen[tests].count(now))return seen[tests][now];
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]>k[j]&&k[i]>k[p])a1.push_back(k);
if(k[j]>k[p]&&k[j]>k[i])a2.push_back(k);
if(k[p]>k[i]&&k[p]>k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]<k[j]&&k[i]<k[p])a1.push_back(k);
if(k[j]<k[p]&&k[j]<k[i])a2.push_back(k);
if(k[p]<k[i]&&k[p]<k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if((k[i]<k[j])^(k[i]<k[p]))a1.push_back(k);
if((k[j]<k[p])^(k[j]<k[i]))a2.push_back(k);
if((k[p]<k[i])^(k[p]<k[j]))a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
for(int q=0;q<6;q++)
{
if(i==q||j==q||p==q)continue;
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
int ans=-1;
bool spec=0;
if(k[q]>k[i]&&k[q]>k[j]&&k[q]>k[p])spec=1;
if(spec||k[q]<k[i])
{
if(ans==-1||k[ans]>k[i])ans=i;
}
if(spec||k[q]<k[j])
{
if(ans==-1||k[ans]>k[j])ans=j;
}
if(spec||k[q]<k[p])
{
if(ans==-1||k[ans]>k[p])ans=p;
}
if(ans==i)a1.push_back(k);
if(ans==j)a2.push_back(k);
if(ans==p)a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
seen[tests][now]=0;
return 0;
}
int output[6];
void write(int tests,vector< vector<int> > &now)
{
//cout<<tests<<" "<<now.size()<<endl;
if(now.size()<=1)
{
assert(now.size()==1);
for(int i=0;i<6;i++)
{
output[now[0][i]]=i+1;
}
return;
}
//if(seen[tests].count(now))return seen[tests][now];
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]>k[j]&&k[i]>k[p])a1.push_back(k);
if(k[j]>k[p]&&k[j]>k[i])a2.push_back(k);
if(k[p]>k[i]&&k[p]>k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getHeaviest(i+1,j+1,p+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]<k[j]&&k[i]<k[p])a1.push_back(k);
if(k[j]<k[p]&&k[j]<k[i])a2.push_back(k);
if(k[p]<k[i]&&k[p]<k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getLightest(i+1,j+1,p+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if((k[i]<k[j])^(k[i]<k[p]))a1.push_back(k);
if((k[j]<k[p])^(k[j]<k[i]))a2.push_back(k);
if((k[p]<k[i])^(k[p]<k[j]))a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getMedian(i+1,j+1,p+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
for(int q=0;q<6;q++)
{
if(i==q||j==q||p==q)continue;
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
int ans=-1;
bool spec=0;
if(k[q]>k[i]&&k[q]>k[j]&&k[q]>k[p])spec=1;
if(spec||k[q]<k[i])
{
if(ans==-1||k[ans]>k[i])ans=i;
}
if(spec||k[q]<k[j])
{
if(ans==-1||k[ans]>k[j])ans=j;
}
if(spec||k[q]<k[p])
{
if(ans==-1||k[ans]>k[p])ans=p;
}
if(ans==i)a1.push_back(k);
if(ans==j)a2.push_back(k);
if(ans==p)a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getNextLightest(i+1,j+1,p+1,q+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
assert(0==1);
}
void init(int T)
{
all={};
for(int i=0;i<=5;i++)
all.push_back(i);
active={};
do
{
active.push_back(all);
}
while(next_permutation(all.begin(),all.end()));
//assert(can(7,active));
assert(can(6,active));
}
void orderCoins()
{
all={};
for(int i=0;i<=5;i++)
all.push_back(i);
active={};
do
{
active.push_back(all);
}
while(next_permutation(all.begin(),all.end()));
write(6,active);
answer(output);
//write(8,active);
}
/*
int main()
{
init(12);
orderCoins();
}
*/
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||