#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[7];
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);
}
Compilation message
scales.cpp: In function 'int makeorder(int, std::vector<int>, int)':
scales.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<list.size(); j++){
^
scales.cpp:74:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<list.size(); j++){
^
scales.cpp: At global scope:
scales.cpp:94:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 4 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2068 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 7 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 8 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 9 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 10 |
Correct |
13 ms |
2068 KB |
Output is correct |
| 11 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 12 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 13 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 14 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 15 |
Correct |
13 ms |
2068 KB |
Output is correct |
| 16 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 17 |
Correct |
13 ms |
2068 KB |
Output is correct |
| 18 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 19 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 20 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 21 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 22 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 23 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 24 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 25 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 26 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 27 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 28 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 29 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 30 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 31 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 32 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 33 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 34 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 35 |
Correct |
13 ms |
2068 KB |
Output is correct |
| 36 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 37 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 38 |
Correct |
13 ms |
2068 KB |
Output is correct |
| 39 |
Correct |
9 ms |
2068 KB |
Output is correct |
| 40 |
Correct |
9 ms |
2068 KB |
Output is correct |
