# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
31174 | cscandkswon | 저울 (IOI15_scales) | C++14 | 13 ms | 2068 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXQ=120;
const int MAXP=720;
struct Question{
int type, a, b, c, d;
} Q[MAXQ];
struct Permutation{
int A[7];
} P[MAXP];
int order[5000];
int getL(Permutation list, int a, int b, int c){
if(list.A[a]<list.A[b] && list.A[a]<list.A[c]) return 0;
else if(list.A[b]<list.A[c]) return 1;
return 2;
}
int getH(Permutation list, int a, int b, int c){
if(list.A[a]>list.A[b] && list.A[a]>list.A[c]) return 0;
else if(list.A[b]>list.A[c]) return 1;
return 2;
}
int getM(Permutation list, int a, int b, int c){
if(min(list.A[b], list.A[c])<list.A[a]&&list.A[a]<max(list.A[b], list.A[c])) return 0;
else if(min(list.A[a], list.A[c])<list.A[b]&&list.A[b]<max(list.A[a], list.A[c])) return 1;
return 2;
}
int getN(Permutation list, int a, int b, int c, int d){
int x=(list.A[d]<list.A[a]), y=(list.A[d]<list.A[b]), z=(list.A[d]<list.A[c]);
if(x&&y&&z) return getL(list, a, b, c);
else if(x&&y){
if(list.A[a]<list.A[b]) return 0;
else return 1;
}
else if(x&&z){
if(list.A[a]<list.A[c]) return 0;
else return 2;
}
else if(y&&z){
if(list.A[b]<list.A[c]) return 1;
return 2;
}
else if(x) return 0;
else if(y) return 1;
else if(z) return 2;
else return getL(list, a, b, c);
}
int makeorder(int lev, vector<int> list, int idx){
if(lev==6){
if(list.size()==1)
order[idx]=list[0];
return 1;
}
int i, j, rv, cnt[3]={0};
for(i=0; i<MAXQ; i++){
cnt[0]=cnt[1]=cnt[2]=0;
for(j=0; j<list.size(); j++){
if(Q[i].type==1) rv=getL(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
else if(Q[i].type==2) rv=getH(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
else if(Q[i].type==3) rv=getM(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
else rv=getN(P[list[j]], Q[i].a, Q[i].b, Q[i].c, Q[i].d);
cnt[rv]++;
}
if(max(cnt[0], max(cnt[1], cnt[2]))-min(cnt[0], min(cnt[1], cnt[2]))<=1){
vector<int> lst[3];
for(j=0; j<list.size(); j++){
if(Q[i].type==1) rv=getL(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
else if(Q[i].type==2) rv=getH(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
else if(Q[i].type==3) rv=getM(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
else rv=getN(P[list[j]], Q[i].a, Q[i].b, Q[i].c, Q[i].d);
lst[rv].push_back(list[j]);
}
rv=makeorder(lev+1, lst[0], idx*3-1);
if(!rv) continue;
rv=makeorder(lev+1, lst[1], idx*3);
if(!rv) continue;
rv=makeorder(lev+1, lst[2], idx*3+1);
if(!rv) continue;
order[idx]=i;
return 1;
}
}
return 0;
}
void init(int T) {
int i, j, k, l, idx=0, A[6];
for(i=1; i<=6; i++){
for(j=i+1; j<=6; j++){
for(k=j+1; k<=6; k++){
Q[idx].type=1, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
Q[idx].type=2, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
Q[idx].type=3, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
for(l=1; l<=6; l++) if(l!=i && l!=j && l!=k){
Q[idx].type=4, Q[idx].a=i, Q[idx].b=j, Q[idx].c=k, Q[idx++].d=l;
}
}
}
}
idx=0;
for(i=1; i<=6; i++) A[i]=i;
do{
for(i=1; i<=6; i++) P[idx].A[i]=A[i];
idx++;
}while(next_permutation(A+1, A+7));
vector<int> vec;
for(i=0; i<MAXP; i++) vec.push_back(i);
makeorder(0, vec, 1);
}
void orderCoins() {
int i, idx=1, rv;
for(i=0; i<6; i++){
if(Q[order[idx]].type==1)
rv=getLightest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
else if(Q[order[idx]].type==2)
rv=getHeaviest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
else if(Q[order[idx]].type==3)
rv=getMedian(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
else
rv=getNextLightest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c, Q[order[idx]].d);
if(rv==Q[order[idx]].a) rv=0;
else if(rv==Q[order[idx]].b) rv=1;
else rv=2;
if(rv==0) idx=idx*3-1;
else if(rv==1) idx=idx*3;
else idx=idx*3+1;
}
idx=order[idx];
int ans[6];
for(i=1; i<=6; i++){
ans[P[idx].A[i]-1]=i;
}
answer(ans);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |