# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
411265 | nxteru | 저울 (IOI15_scales) | C++14 | 1096 ms | 460 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
void init(int T) {
/* ... */
}
struct data{
vector<vector<int>>x;
vector<vector<int>> addHeaviest(vector<int>a,int p){
vector<vector<int>>res;
for(auto v:x){
bool ok=true;
for(auto i:a){
if(v[i]>v[p])ok=false;
}
if(ok)res.push_back(v);
}
return res;
}
vector<vector<int>> addLightest(vector<int>a,int p){
vector<vector<int>>res;
for(auto v:x){
bool ok=true;
for(auto i:a){
if(v[i]<v[p])ok=false;
}
if(ok)res.push_back(v);
}
return res;
}
vector<vector<int>> addMedian(vector<int>a,int p){
vector<vector<int>>res;
for(auto v:x){
bool ok=true;
int ma=-1,mi=10;
for(auto i:a){
ma=max(ma,v[i]);
mi=min(mi,v[i]);
}
if(ma==v[p]||mi==v[p])ok=false;
if(ok)res.push_back(v);
}
return res;
}
vector<vector<int>> addNext(vector<int>a,int q,int p){
vector<vector<int>>res;
for(auto v:x){
bool ok=true;
int mi=10,mii=10;
for(auto i:a){
mii=min(mii,v[i]);
if(v[q]<v[i])mi=min(mi,v[i]);
}
if(mi==10)mi=mii;
if(mi!=v[p])ok=false;
if(ok)res.push_back(v);
}
return res;
}
vector<int> Next(void){
int mi=1000;
vector<int>res;
vector<int>p={0,1,2,3,4,5};
bool vis1[6*6*6],vis2[6*6*6*6];
for(int i=0;i<6*6*6;i++)vis1[i]=false;
for(int i=0;i<6*6*6*6;i++)vis2[i]=false;
do{
int s=p[0]+p[1]*6+p[2]*6*6;
if(!vis1[s]){
vector<int>a;
for(int i=0;i<3;i++)a.push_back(p[i]);
int ma=0;
for(int i=0;i<3;i++)ma=max(int(addHeaviest(a,a[i]).size()),ma);
if(ma<mi){
mi=ma;
res=a;
res.push_back(0);
}
ma=0;
for(int i=0;i<3;i++)ma=max(int(addLightest(a,a[i]).size()),ma);
if(ma<mi){
mi=ma;
res=a;
res.push_back(1);
}
ma=0;
for(int i=0;i<3;i++)ma=max(int(addMedian(a,a[i]).size()),ma);
if(ma<mi){
mi=ma;
res=a;
res.push_back(2);
}
vis1[s]=true;
}
s+=p[3]*6*6*6;
if(!vis2[s]){
vector<int>a;
for(int i=0;i<3;i++)a.push_back(p[i]);
int ma=0;
for(int i=0;i<3;i++)ma=max(int(addNext(a,p[3],a[i]).size()),ma);
if(ma<mi){
mi=ma;
res=a;
res.push_back(p[3]);
res.push_back(3);
}
vis2[s]=true;
}
}while(next_permutation(p.begin(),p.end()));
return res;
}
};
void orderCoins() {
data d;
vector<int>p={0,1,2,3,4,5};
do{
d.x.push_back(p);
}while(next_permutation(p.begin(),p.end()));
while(d.x.size()>1){
vector<int>q=d.Next();
if(q.back()==0){
q.pop_back();
d.x=d.addHeaviest(q,getHeaviest(q[0]+1,q[1]+1,q[2]+1)-1);
}else if(q.back()==1){
q.pop_back();
d.x=d.addLightest(q,getLightest(q[0]+1,q[1]+1,q[2]+1)-1);
}else if(q.back()==2){
q.pop_back();
d.x=d.addMedian(q,getMedian(q[0]+1,q[1]+1,q[2]+1)-1);
}else{
q.pop_back();
int x=q.back();
q.pop_back();
d.x=d.addNext(q,x,getNextLightest(q[0]+1,q[1]+1,q[2]+1,x+1)-1);
}
}
int ans[6];
for(int i=0;i<6;i++){
ans[d.x[0][i]]=i+1;
}
answer(ans);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |