| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 126040 | dragonslayerit | 저울 (IOI15_scales) | C++14 | 48 ms | 504 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <vector>
#include <array>
#include <algorithm>
#include <cassert>
void init(int T) {
(void)T;
}
//possible ranks of coins
std::vector<std::array<int,6> > possible;
int consider1(int a,int b,int c){
int remain[3][3]={{0,0,0},{0,0,0},{0,0,0}};
int vs[3]={a,b,c};
int xs[3]={0,1,2};
for(auto ps:possible){
std::sort(xs,xs+3,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
for(int i=0;i<3;i++){
remain[i][xs[i]]++;
}
}
int best=720;
for(int i=0;i<3;i++){
best=std::min(best,*std::max_element(remain[i],remain[i]+3));
}
return best;
}
int consider2(int a,int b,int c,int d){
int remain[3]={0,0,0};
int vs[4]={a,b,c,d};
int xs[4]={0,1,2,3};
for(auto ps:possible){
std::sort(xs,xs+4,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
remain[xs[(std::find(xs,xs+4,3)-xs+1)%4]]++;
}
return *std::max_element(remain,remain+3);
}
int query(int a,int b,int c,int t){
a++,b++,c++;
if(t==0) return getLightest(a,b,c)-1;
if(t==1) return getMedian(a,b,c)-1;
if(t==2) return getHeaviest(a,b,c)-1;
assert(0);
}
void reduce1(int a,int b,int c){
std::vector<std::array<int,6> > remain[3][3];
int vs[3]={a,b,c};
int xs[3]={0,1,2};
for(auto ps:possible){
std::sort(xs,xs+3,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
for(int i=0;i<3;i++){
remain[i][xs[i]].push_back(ps);
}
}
int worst[3]={0,0,0};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
worst[i]=std::max<int>(worst[i],remain[i][j].size());
}
}
int type=std::min_element(worst,worst+3)-worst;
int which=std::find(vs,vs+3,query(a,b,c,type))-vs;
possible=remain[type][which];
}
void reduce2(int a,int b,int c,int d){
//fprintf(stderr,"DDDDDDDDDDDD\n");
std::vector<std::array<int,6> > remain[3];
int vs[4]={a,b,c,d};
int xs[4]={0,1,2,3};
for(auto ps:possible){
std::sort(xs,xs+4,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
remain[xs[(std::find(xs,xs+4,3)-xs+1)%4]].push_back(ps);
}
int which=std::find(vs,vs+3,getNextLightest(a+1,b+1,c+1,d+1)-1)-vs;
possible=remain[which];
}
void orderCoins() {
//init
{
std::array<int,6> ps({0,1,2,3,4,5});
do{
possible.push_back(ps);
}while(std::next_permutation(ps.begin(),ps.end()));
}
//main
while(possible.size()>1){
std::array<int,5> best={720,10,10,10,10};
for(int a=0;a<6;a++){
for(int b=0;b<a;b++){
for(int c=0;c<b;c++){
best=std::min(best,{consider1(a,b,c),a,b,c,-1});
for(int d=0;d<6;d++){
if(d==a||d==b||d==c) continue;
best=std::min(best,{consider2(a,b,c,d),a,b,c,d});
}
}
}
}
//printf("expect %d permutations\n",best[0]);
if(best[4]==-1){
reduce1(best[1],best[2],best[3]);
}else{
reduce2(best[1],best[2],best[3],best[4]);
}
/*
printf("%d permuations remaining\n",(int)possible.size());
if(possible.size()<=10){
for(auto ps:possible){
printf("%d %d %d %d %d %d\n",ps[0],ps[1],ps[2],ps[3],ps[4],ps[5]);
}
}
*/
}
assert(possible.size()==1);
int coins[6]={1,2,3,4,5,6};
std::sort(coins,coins+6,[](int i,int j){return possible[0][i-1]<possible[0][j-1];});
answer(coins);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||