| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038720 |
2024-07-30T06:49:42 Z |
shenfe1 |
Scales (IOI15_scales) |
C++17 |
|
219 ms |
864 KB |
#include <bits/stdc++.h>
#include "scales.h"
#pragma GCC optimize("Ofast")
#define ll long long
#define pb push_back
#define sz(s) (int)s.size()
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int L=6;
map<vector<vector<int>>,pii> mp;
map<vector<vector<int>>,pair<pii,pii>> qr;
int pos[7];
bool check(int i,int j,int k,int d,vector<int> x){
for(int j=0;j<6;j++)pos[x[j]]=j;
if(pos[i]<pos[d]){
if(pos[i]<min(pos[j],pos[k])&&max(pos[j],pos[k])<pos[d])return 1;
}
else{
if(!(pos[d]<=pos[j]&&pos[j]<=pos[i])&&!(pos[d]<=pos[k]&&pos[k]<=pos[i]))return 1;
}
return 0;
}
int solve(vector<vector<int>> vec,int pot,int lev){
if(sz(vec)<=1)return 0;
if(mp.count(vec))return mp[vec].F;
pii res={100,0};
{
for(int i=1;i<=L;i++){
for(int j=i+1;j<=L;j++){
for(int k=j+1;k<=L;k++){
vector<vector<int>> a,b,c;
for(auto x:vec){
for(int f=0;f<L;f++)pos[x[f]]=f;
if(pos[i]<=pos[j]&&pos[i]<=pos[k])a.pb(x);
else if(pos[j]<=pos[i]&&pos[j]<=pos[k])b.pb(x);
else c.pb(x);
}
if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
if(cur==6-lev){
mp[vec]={cur,0};
qr[vec]={{i,j},{k,0}};
return 6-lev;
}
}
}
}
}
{
for(int i=1;i<=L;i++){
for(int j=i+1;j<=L;j++){
for(int k=j+1;k<=L;k++){
vector<vector<int>> a,b,c;
for(auto x:vec){
for(int f=0;f<L;f++)pos[x[f]]=f;
if(min(pos[j],pos[k])<pos[i]&&pos[i]<max(pos[j],pos[k]))a.pb(x);
else if(min(pos[i],pos[k])<pos[j]&&pos[j]<max(pos[i],pos[k]))b.pb(x);
else c.pb(x);
}
if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
if(cur==6-lev){
mp[vec]={cur,1};
qr[vec]={{i,j},{k,0}};
return 6-lev;
}
}
}
}
}
{
for(int i=1;i<=L;i++){
for(int j=i+1;j<=L;j++){
for(int k=j+1;k<=L;k++){
vector<vector<int>> a,b,c;
for(auto x:vec){
for(int f=0;f<L;f++)pos[x[f]]=f;
if(pos[i]>=pos[j]&&pos[i]>=pos[k])a.pb(x);
else if(pos[j]>=pos[i]&&pos[j]>=pos[k])b.pb(x);
else c.pb(x);
}
if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
if(cur==6-lev){
mp[vec]={cur,2};
qr[vec]={{i,j},{k,0}};
return 6-lev;
}
}
}
}
}
{
for(int i=1;i<=L;i++){
assert(i<=L);
for(int j=i+1;j<=L;j++){
if(i>L){
cout<<i<<"\n";
exit(0);
}
assert(i<=L&&j<=L);
for(int k=j+1;k<=L;k++){
assert(i<=L&&j<=L&&k<=L);
for(int d=1;d<=L;d++){
if(i==d||j==d||k==d)continue;
assert(d<=6);
assert(i<=6&&j<=6&&d<=6);
vector<vector<int>> a,b,c;
for(auto x:vec){
if(check(i,j,k,d,x))a.pb(x);
else if(check(j,i,k,d,x))b.pb(x);
else c.pb(x);
}
if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
assert(sz(a)+sz(b)+sz(c)==sz(vec));
int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
if(cur==6-lev){
mp[vec]={cur,3};
qr[vec]={{i,j},{k,d}};
return 6-lev;
}
}
}
}
}
}
}
void init(int T){
vector<int> v;
for(int i=1;i<=L;i++)v.pb(i);
vector<vector<int>> vec;
do{
vec.pb(v);
}while(next_permutation(all(v)));
solve(vec,729,0);
}
void orderCoins(){
vector<int> v;
for(int i=1;i<=L;i++)v.pb(i);
vector<vector<int>> vec;
do{
vec.pb(v);
}while(next_permutation(all(v)));
while(sz(vec)>1){
int zap=mp[vec].S;
int res;
pair<pii,int> query={qr[vec].F,qr[vec].S.F};
if(zap==0){
res=getLightest(query.F.F,query.F.S,query.S);
vector<vector<int>> nw;
for(auto x:vec){
int pos[7];
for(int j=0;j<6;j++)pos[x[j]]=j;
if(pos[res]<=min({pos[query.F.F],pos[query.F.S],pos[query.S]}))nw.pb(x);
}
swap(nw,vec);
}
else if(zap==1){
res=getMedian(query.F.F,query.F.S,query.S);
vector<vector<int>> nw;
for(auto x:vec){
int pos[7];
for(int j=0;j<6;j++)pos[x[j]]=j;
if(pos[res]>min({pos[query.F.F],pos[query.F.S],pos[query.S]})&&pos[res]<max({pos[query.F.F],pos[query.F.S],pos[query.S]}))nw.pb(x);
}
swap(nw,vec);
}
else if(zap==2){
res=getHeaviest(query.F.F,query.F.S,query.S);
vector<vector<int>> nw;
for(auto x:vec){
int pos[7];
for(int j=0;j<6;j++)pos[x[j]]=j;
if(pos[res]>=max({pos[query.F.F],pos[query.F.S],pos[query.S]}))nw.pb(x);
}
swap(nw,vec);
}
else{
res=getNextLightest(query.F.F,query.F.S,query.S,qr[vec].S.S);
vector<vector<int>> nw;
for(auto x:vec){
int pos[7];
for(int j=0;j<6;j++)pos[x[j]]=j;
int P=pos[qr[vec].S.S];
if(pos[res]<P){
if(pos[res]<=min({pos[query.F.F],pos[query.F.S],pos[query.S]})&&max({pos[query.F.F],pos[query.F.S],pos[query.S]})<P){
nw.pb(x);
}
}
else{
if(!(P<pos[query.F.F]&&pos[query.F.F]<pos[res])&&!(P<pos[query.F.S]&&pos[query.F.S]<pos[res])&&!(P<pos[query.S]&&pos[query.S]<pos[res]))nw.pb(x);
}
}
swap(nw,vec);
}
}
int C[6];
for(int i=0;i<6;i++)C[i]=vec[0][i];
answer(C);
}
Compilation message
scales.cpp: In function 'bool check(int, int, int, int, std::vector<int>)':
scales.cpp:23:13: warning: declaration of 'int j' shadows a parameter [-Wshadow]
23 | for(int j=0;j<6;j++)pos[x[j]]=j;
| ^
scales.cpp:22:22: note: shadowed declaration is here
22 | bool check(int i,int j,int k,int d,vector<int> x){
| ~~~~^
scales.cpp: In function 'int solve(std::vector<std::vector<int> >, int, int)':
scales.cpp:36:9: warning: variable 'res' set but not used [-Wunused-but-set-variable]
36 | pii res={100,0};
| ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:139:15: warning: unused parameter 'T' [-Wunused-parameter]
139 | void init(int T){
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:164:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
164 | int pos[7];
| ^~~
scales.cpp:20:5: note: shadowed declaration is here
20 | int pos[7];
| ^~~
scales.cpp:174:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
174 | int pos[7];
| ^~~
scales.cpp:20:5: note: shadowed declaration is here
20 | int pos[7];
| ^~~
scales.cpp:184:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
184 | int pos[7];
| ^~~
scales.cpp:20:5: note: shadowed declaration is here
20 | int pos[7];
| ^~~
scales.cpp:195:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
195 | int pos[7];
| ^~~
scales.cpp:20:5: note: shadowed declaration is here
20 | int pos[7];
| ^~~
scales.cpp: In function 'int solve(std::vector<std::vector<int> >, int, int)':
scales.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
137 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
184 ms |
844 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
192 ms |
860 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
198 ms |
860 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
188 ms |
844 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
198 ms |
848 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
182 ms |
844 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
189 ms |
856 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
192 ms |
840 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
189 ms |
860 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
181 ms |
844 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
190 ms |
844 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
200 ms |
844 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
219 ms |
848 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
189 ms |
848 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
192 ms |
848 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
202 ms |
848 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
206 ms |
848 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
195 ms |
844 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
215 ms |
844 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
191 ms |
860 KB |
Execution killed with signal 11 |
| 21 |
Runtime error |
188 ms |
684 KB |
Execution killed with signal 11 |
| 22 |
Runtime error |
181 ms |
840 KB |
Execution killed with signal 11 |
| 23 |
Runtime error |
188 ms |
848 KB |
Execution killed with signal 11 |
| 24 |
Runtime error |
197 ms |
848 KB |
Execution killed with signal 11 |
| 25 |
Runtime error |
193 ms |
844 KB |
Execution killed with signal 11 |
| 26 |
Runtime error |
196 ms |
844 KB |
Execution killed with signal 11 |
| 27 |
Runtime error |
192 ms |
844 KB |
Execution killed with signal 11 |
| 28 |
Runtime error |
187 ms |
860 KB |
Execution killed with signal 11 |
| 29 |
Runtime error |
197 ms |
864 KB |
Execution killed with signal 11 |
| 30 |
Runtime error |
193 ms |
848 KB |
Execution killed with signal 11 |
| 31 |
Runtime error |
190 ms |
840 KB |
Execution killed with signal 11 |
| 32 |
Runtime error |
190 ms |
844 KB |
Execution killed with signal 11 |
| 33 |
Runtime error |
204 ms |
844 KB |
Execution killed with signal 11 |
| 34 |
Runtime error |
191 ms |
848 KB |
Execution killed with signal 11 |
| 35 |
Runtime error |
192 ms |
844 KB |
Execution killed with signal 11 |
| 36 |
Runtime error |
199 ms |
848 KB |
Execution killed with signal 11 |
| 37 |
Runtime error |
188 ms |
848 KB |
Execution killed with signal 11 |
| 38 |
Runtime error |
190 ms |
844 KB |
Execution killed with signal 11 |
| 39 |
Runtime error |
200 ms |
860 KB |
Execution killed with signal 11 |
| 40 |
Runtime error |
193 ms |
848 KB |
Execution killed with signal 11 |
