| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1055258 | Faisal_Saqib | 저울 (IOI15_scales) | C++17 | 685 ms | 7192 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "scales.h"
// void answer(int C[]);
// int getMedian(int A, int B, int C);
// int getHeaviest(int A, int B, int C);
// int getLightest(int A, int B, int C);
// int getNextLightest(int A, int B, int C, int D);
using namespace std;
#include <bits/stdc++.h>
// #include "scales.h"
// void answer(int C[]);
// int getMedian(int A, int B, int C);
// int getHeaviest(int A, int B, int C);
// int getLightest(int A, int B, int C);
// int getNextLightest(int A, int B, int C, int D);
using namespace std;
#define question array<int,5>
#define permutation array<int,6>
#define possibility vector<permutation>
map<possibility,question> best_question;
map<possibility,int> min_queries;
int ask(permutation&p,question&q)
{
permutation ind;
for(int i=0;i<p.size();i++)
ind[p[i]-1]=i;
int A=q[1]; // A= 1
int B=q[2];// B=2
int C=q[3];
int D=q[4];
if(q[0]==1)//heaviest
{
if (ind[A-1] > ind[B-1] && ind[A-1] > ind[C-1])
return A;
if (ind[B-1] > ind[A-1] && ind[B-1] > ind[C-1])
return B;
return C;
}
else if(q[0]==2)// lightest
{
if (ind[A-1] < ind[B-1] && ind[A-1] < ind[C-1])
return A;
if (ind[B-1] < ind[A-1] && ind[B-1] < ind[C-1])
return B;
return C;
}
else if(q[0]==3) // medians
{
if (ind[B-1] < ind[A-1] && ind[A-1] < ind[C-1])
return A;
if (ind[C-1] < ind[A-1] && ind[A-1] < ind[B-1])
return A;
if (ind[A-1] < ind[B-1] && ind[B-1] < ind[C-1])
return B;
if (ind[C-1] < ind[B-1] && ind[B-1] < ind[A-1])
return B;
return C;
}
else
{
int allLess = 1;
if (ind[A-1] > ind[D-1] || ind[B-1] > ind[D-1] || ind[C-1] > ind[D-1])
allLess = 0;
if (allLess == 1) {
if (ind[A-1] < ind[B-1] && ind[A-1] < ind[C-1])
return A;
if (ind[B-1] < ind[A-1] && ind[B-1] < ind[C-1])
return B;
return C;
}
if (ind[A-1] > ind[D-1]) {
if ((ind[A-1] < ind[B-1] || ind[B-1] < ind[D-1]) &&
(ind[A-1] < ind[C-1] || ind[C-1] < ind[D-1]))
return A;
}
if (ind[B-1] > ind[D-1]) {
if ((ind[B-1] < ind[A-1] || ind[A-1] < ind[D-1]) &&
(ind[B-1] < ind[C-1] || ind[C-1] < ind[D-1]))
return B;
}
return C;
}
}
possibility outcomes(question&q,possibility&cur,int&answer)
{
possibility remaining;
for(auto&perm:cur)
{
if(ask(perm,q)==answer)
{
remaining.push_back(perm);
}
}
return remaining;
}
void find_solution(possibility& cur,int lim=730,int depth=6)
{
if(cur.size()<=1)
{
min_queries[cur]=0;
return;
}
if(best_question.find(cur)!=best_question.end() or min_queries.find(cur)!=min_queries.end())
return;
if(cur.size()>lim or depth==0)
{
min_queries[cur]=1000;
return;
}
question q;
question ansp;
min_queries[cur]=1000;
for(q[0]=1;q[0]<=4;q[0]++)
{
for(q[1]=1;q[1]<=6;q[1]++)
{
for(q[2]=q[1]+1;q[2]<=6;q[2]++)
{
for(q[3]=q[2]+1;q[3]<=6;q[3]++)
{
for(q[4]=1;q[4]<=6;q[4]++)
{
if(q[0]!=4 and q[4]!=1)continue;
if(q[0]==4 and (q[4]==q[1] or q[4]==q[2] or q[4]==q[3]))continue;
possibility result_in_a;
possibility result_in_b;
possibility result_in_c;
result_in_a = outcomes(q,cur,q[1]);
result_in_b = outcomes(q,cur,q[2]);
result_in_c = outcomes(q,cur,q[3]);
int mx_sz=max({result_in_a.size(),result_in_b.size(),result_in_c.size()});
if(mx_sz>(lim/3))continue;
find_solution(result_in_a,lim/3,depth-1);
find_solution(result_in_b,lim/3,depth-1);
find_solution(result_in_c,lim/3,depth-1);
int result=1+max({min_queries[result_in_a],min_queries[result_in_b],min_queries[result_in_c]});
if(result<min_queries[cur])
{
min_queries[cur]=result;
ansp=q;
if(min_queries[cur]==6)
{
best_question[cur]=ansp;
return;
}
}
}
}
}
}
}
best_question[cur]=ansp;
}
void init(int TPPA)
{
possibility total;
permutation a={1,2,3,4,5,6};
do
{
total.push_back(a);
}while(next_permutation(begin(a),end(a)));
find_solution(total);
}
void orderCoins() {
possibility total;
permutation a={1,2,3,4,5,6};
do
{
total.push_back(a);
}while(next_permutation(begin(a),end(a)));
while(total.size()!=1)
{
question q=best_question[total];
int ans=0;
if(q[0]==1)
{
ans=getHeaviest(q[1],q[2],q[3]);
}
else if(q[0]==2)
{
ans=getLightest(q[1],q[2],q[3]);
}
else if(q[0]==3)
{
ans=getMedian(q[1],q[2],q[3]);
}
else{
ans=getNextLightest(q[1],q[2],q[3],q[4]);
// q[0]==4
}
possibility nxt=outcomes(q,total,ans);
total=nxt;
}
int anpp[6];
for(auto&j:total)
{
for(int i=0;i<6;i++)
{
anpp[i]=j[i];
}
}
answer(anpp);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||