| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1038713 | shenfe1 | Scales (IOI15_scales) | C++17 | 3 ms | 944 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 solve(vector<vector<int>> vec,int pot,int lev){
if(sz(vec)<=1)return 0;
if(mp.count(vec))return mp[vec].F;
assert(sz(vec)<=pot);
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){
int pos[7];
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){
int pos[7];
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){
int pos[7];
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;
}
}
}
}
}
{
// cout<<L<<"\n";
for(int i=1;i<=L;i++){
assert(i<=L);
for(int j=i+1;j<=L;j++){
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){
int pos[7];
for(int f=0;f<L;f++)pos[x[f]]=f;
{
if(pos[i]<pos[d]){
if(pos[i]<min(pos[j],pos[k])&&max(pos[j],pos[k])<pos[d])a.pb(x);
}
else{
if(!(pos[d]<=pos[j]&&pos[j]<=pos[i])&&!(pos[d]<=pos[k]&&pos[k]<=pos[i]))a.pb(x);
}
}
{
if(pos[j]<pos[d]){
if(pos[j]<min(pos[i],pos[k])&&max(pos[i],pos[k])<pos[d])b.pb(x);
}
else{
if(!(pos[d]<=pos[i]&&pos[i]<=pos[j])&&!(pos[d]<=pos[k]&&pos[k]<=pos[j]))b.pb(x);
}
}
{
if(pos[k]<pos[d]){
if(pos[k]<min(pos[i],pos[j])&&max(pos[i],pos[j])<pos[d])c.pb(x);
}
else{
if(!(pos[d]<=pos[i]&&pos[i]<=pos[k])&&!(pos[d]<=pos[j]&&pos[j]<=pos[k]))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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||