#include<bits/stdc++.h>
using namespace std;
#ifndef WEAK
#include"scales.h"
#else
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wreturn-type"
int coins[6],pos[6],qtime;
int Init(){ return 1; }
void orderCoins(){
cout<<"orderCoins: "<<endl;
for(int i=0;i<6;++i)cin>>coins[i],pos[coins[i]]=i;
}
void answer(int *a){
cout<<"answer: ";
for(int i=0;i<6;++i)cout<<a[i]<<" "; cout<<endl;
cout<<"Query "<<qtime<<" times"<<endl;
}
int getHeaviest(int i,int j,int k){
++qtime;
cout<<"getHeaviest "<<i<<" "<<j<<" "<<k<<endl;
if(pos[i]>pos[j] && pos[i]>pos[k])return i;
if(pos[j]>pos[i] && pos[j]>pos[k])return j;
if(pos[k]>pos[i] && pos[k]>pos[j])return k;
}
int getLightest(int i,int j,int k){
++qtime;
cout<<"getLightest "<<i<<" "<<j<<" "<<k<<endl;
if(pos[i]<pos[j] && pos[i]<pos[k])return i;
if(pos[j]<pos[i] && pos[j]<pos[k])return j;
if(pos[k]<pos[i] && pos[k]<pos[j])return k;
}
int getMedian(int i,int j,int k){
++qtime;
cout<<"getMedian "<<i<<" "<<j<<" "<<k<<endl;
if((pos[i]>pos[j])^(pos[i]>pos[k]))return i;
if((pos[j]>pos[i])^(pos[j]>pos[k]))return j;
if((pos[k]>pos[i])^(pos[k]>pos[j]))return k;
}
int getNextLightest(int i,int j,int k,int l){
++qtime;
cout<<"getNextLightest "<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
pair<int,int> pp[4]={{pos[i],i},{pos[j],j},{pos[k],k},{pos[l],l}};
sort(pp,pp+4);
if(pp[3].second==l)return pp[0].second;
for(int i=0;i<3;++i)if(pp[i].second==l)return pp[i+1].second;
}
#pragma GCC diagnostic pop
#endif
struct operation{
int type,arg1,arg2,arg3,arg4;
};
vector<operation> ops;
int go(vector<vector<int>> &now,bool okQ=0){
if(now.size()<=1u)return 1;
auto pnow=[&](){
cout<<"now: "<<endl;
for(auto &v:now){
for(int i:v)cout<<i<<" ";
cout<<endl;
}
};
// pnow();
// cout<<"okQ: "<<okQ<<endl;
int pos[8];
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wreturn-type"
auto _sim_getHeaviest=[&](const int i,const int j,const int k){
if(pos[i]>pos[j] && pos[i]>pos[k])return i;
if(pos[j]>pos[i] && pos[j]>pos[k])return j;
if(pos[k]>pos[i] && pos[k]>pos[j])return k;
};
auto _sim_getLightest=[&](const int i,const int j,const int k){
if(pos[i]<pos[j] && pos[i]<pos[k])return i;
if(pos[j]<pos[i] && pos[j]<pos[k])return j;
if(pos[k]<pos[i] && pos[k]<pos[j])return k;
};
auto _sim_getMedian=[&](const int i,const int j,const int k){
if((pos[i]>pos[j])^(pos[i]>pos[k]))return i;
if((pos[j]>pos[i])^(pos[j]>pos[k]))return j;
if((pos[k]>pos[i])^(pos[k]>pos[j]))return k;
};
auto _sim_getNextLightest=[&](const int i,const int j,const int k,const int l){
pair<int,int> pp[4]={{pos[i],i},{pos[j],j},{pos[k],k},{pos[l],l}};
sort(pp,pp+4);
if(pp[3].second==l)return pp[0].second;
for(int i=0;i<3;++i)if(pp[i].second==l)return pp[i+1].second;
};
#pragma GCC diagnostic pop
for(int i=1;i<=4;++i){
for(int j=i+1;j<=5;++j){
for(int k=j+1;k<=6;++k){
int r1=0,r2=0,r3=0,lim=(now.size()+2)/3;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getHeaviest(i,j,k);
if(r==i)++r1;
if(r==j)++r2;
if(r==k)++r3;
}
// cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
if(r1<=lim && r2<=lim && r3<=lim){
vector<vector<int>> v1,v2,v3;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getHeaviest(i,j,k);
if(r==i)v1.push_back(v);
if(r==j)v2.push_back(v);
if(r==k)v3.push_back(v);
}
int ok=go(v1)+go(v2)+go(v3);
if(ok>=3){
if(!okQ)return 1;
vector<vector<int>> tmp;
int r=getHeaviest(i,j,k);
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
if(_sim_getHeaviest(i,j,k)==r)tmp.push_back(v);
}
now.swap(tmp);
assert(go(now,1)==1);
return 1;
}
}
r1=r2=r3=0;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getLightest(i,j,k);
if(r==i)++r1;
if(r==j)++r2;
if(r==k)++r3;
}
// cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
if(r1<=lim && r2<=lim && r3<=lim){
vector<vector<int>> v1,v2,v3;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getLightest(i,j,k);
if(r==i)v1.push_back(v);
if(r==j)v2.push_back(v);
if(r==k)v3.push_back(v);
}
int ok=go(v1)+go(v2)+go(v3);
if(ok>=3){
if(!okQ)return 1;
vector<vector<int>> tmp;
int r=getLightest(i,j,k);
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
if(_sim_getLightest(i,j,k)==r)tmp.push_back(v);
}
now.swap(tmp);
assert(go(now,1)==1);
return 1;
}
}
r1=r2=r3=0;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getMedian(i,j,k);
if(r==i)++r1;
if(r==j)++r2;
if(r==k)++r3;
}
// cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
if(r1<=lim && r2<=lim && r3<=lim){
vector<vector<int>> v1,v2,v3;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getMedian(i,j,k);
if(r==i)v1.push_back(v);
if(r==j)v2.push_back(v);
if(r==k)v3.push_back(v);
}
int ok=go(v1)+go(v2)+go(v3);
if(ok>=3){
if(!okQ)return 1;
vector<vector<int>> tmp;
int r=getMedian(i,j,k);
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
if(_sim_getMedian(i,j,k)==r)tmp.push_back(v);
}
now.swap(tmp);
assert(go(now,1)==1);
return 1;
}
}
for(int l=1;l<=6;++l){
if(l==i || l==j || l==k)continue;
r1=r2=r3=0;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getNextLightest(i,j,k,l);
if(r==i)++r1;
if(r==j)++r2;
if(r==k)++r3;
}
// cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
if(r1<=lim && r2<=lim && r3<=lim){
vector<vector<int>> v1,v2,v3;
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
int r=_sim_getNextLightest(i,j,k,l);
if(r==i)v1.push_back(v);
if(r==j)v2.push_back(v);
if(r==k)v3.push_back(v);
}
int ok=go(v1)+go(v2)+go(v3);
if(ok>=3){
if(!okQ)return 1;
vector<vector<int>> tmp;
int r=getNextLightest(i,j,k,l);
for(auto &v:now){
for(int i=0;i<6;++i)pos[v[i]]=i;
if(_sim_getNextLightest(i,j,k,l)==r)tmp.push_back(v);
}
now.swap(tmp);
assert(go(now,1)==1);
return 1;
}
}
}
}
}
}
return 0;
}
#ifdef WEAK
int main(){
int t=Init(); while(t--){
orderCoins();
int a[6]={1,2,3,4,5,6};
vector<vector<int>> now;
vector<int> tmp(a,a+6);
do{
now.push_back(tmp);
}while(next_permutation(tmp.begin(),tmp.end()));
go(now,1);
for(int i=0;i<6;++i)a[i]=now[0][i];
answer(a);
}
}
#else
void init(int T){}
void orderCoins(){
int a[6]={1,2,3,4,5,6};
vector<vector<int>> now;
vector<int> tmp(a,a+6);
do{
now.push_back(tmp);
}while(next_permutation(tmp.begin(),tmp.end()));
go(now,1);
for(int i=0;i<6;++i)a[i]=now[0][i];
answer(a);
}
#endif
Compilation message
In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (_ghksjhdfkae19ga_ > 1)
^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (i = 0; i < 6; i++) {
^~~
scales.cpp: In lambda function:
scales.cpp:92:17: warning: declaration of 'int i' shadows a parameter [-Wshadow]
for(int i=0;i<3;++i)if(pp[i].second==l)return pp[i+1].second;
^
scales.cpp:88:45: note: shadowed declaration is here
auto _sim_getNextLightest=[&](const int i,const int j,const int k,const int l){
^
scales.cpp: In function 'int go(std::vector<std::vector<int> >&, bool)':
scales.cpp:99:54: warning: conversion to 'int' from 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int r1=0,r2=0,r3=0,lim=(now.size()+2)/3;
~~~~~~~~~~~~~~^~
scales.cpp:101:29: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:111:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:123:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:134:29: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:144:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:156:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:167:29: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:177:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:189:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:202:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:212:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:224:41: warning: declaration of 'i' shadows a previous local [-Wshadow]
for(int i=0;i<6;++i)pos[v[i]]=i;
^
scales.cpp:96:13: note: shadowed declaration is here
for(int i=1;i<=4;++i){
^
scales.cpp:60:10: warning: variable 'pnow' set but not used [-Wunused-but-set-variable]
auto pnow=[&](){
^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:257:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T){}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
632 KB |
Output is correct |
| 2 |
Correct |
779 ms |
640 KB |
Output is correct |
| 3 |
Correct |
722 ms |
652 KB |
Output is correct |
| 4 |
Correct |
718 ms |
696 KB |
Output is correct |
| 5 |
Correct |
775 ms |
764 KB |
Output is correct |
| 6 |
Correct |
781 ms |
776 KB |
Output is correct |
| 7 |
Correct |
772 ms |
836 KB |
Output is correct |
| 8 |
Correct |
768 ms |
836 KB |
Output is correct |
| 9 |
Correct |
737 ms |
836 KB |
Output is correct |
| 10 |
Correct |
764 ms |
836 KB |
Output is correct |
| 11 |
Correct |
839 ms |
836 KB |
Output is correct |
| 12 |
Correct |
885 ms |
836 KB |
Output is correct |
| 13 |
Correct |
893 ms |
836 KB |
Output is correct |
| 14 |
Correct |
830 ms |
836 KB |
Output is correct |
| 15 |
Correct |
842 ms |
864 KB |
Output is correct |
| 16 |
Correct |
814 ms |
864 KB |
Output is correct |
| 17 |
Correct |
800 ms |
864 KB |
Output is correct |
| 18 |
Correct |
779 ms |
864 KB |
Output is correct |
| 19 |
Correct |
827 ms |
864 KB |
Output is correct |
| 20 |
Correct |
767 ms |
864 KB |
Output is correct |
| 21 |
Correct |
835 ms |
864 KB |
Output is correct |
| 22 |
Correct |
736 ms |
864 KB |
Output is correct |
| 23 |
Correct |
843 ms |
876 KB |
Output is correct |
| 24 |
Correct |
787 ms |
876 KB |
Output is correct |
| 25 |
Correct |
737 ms |
876 KB |
Output is correct |
| 26 |
Correct |
727 ms |
876 KB |
Output is correct |
| 27 |
Correct |
760 ms |
876 KB |
Output is correct |
| 28 |
Correct |
759 ms |
876 KB |
Output is correct |
| 29 |
Correct |
718 ms |
876 KB |
Output is correct |
| 30 |
Correct |
701 ms |
876 KB |
Output is correct |
| 31 |
Correct |
704 ms |
876 KB |
Output is correct |
| 32 |
Correct |
751 ms |
876 KB |
Output is correct |
| 33 |
Correct |
813 ms |
876 KB |
Output is correct |
| 34 |
Correct |
741 ms |
876 KB |
Output is correct |
| 35 |
Correct |
753 ms |
880 KB |
Output is correct |
| 36 |
Correct |
723 ms |
880 KB |
Output is correct |
| 37 |
Correct |
761 ms |
880 KB |
Output is correct |
| 38 |
Correct |
759 ms |
880 KB |
Output is correct |
| 39 |
Correct |
771 ms |
880 KB |
Output is correct |
| 40 |
Correct |
750 ms |
892 KB |
Output is correct |
