| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 669194 | alvingogo | Scales (IOI15_scales) | C++14 | 0 ms | 0 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 AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
map<vector<int>,vector<int>(4)> mp;
int po[7]={1,3,9,27,81,243,729};
vector<vector<int> > z;
int get(vector<int> g,int a,int b,int c,int t){
if(t==-1){
for(int i=0;i<6;i++){
if(g[i]==a || g[i]==b || g[i]==c){
return g[i];
}
}
}
else if(t==-3){
for(int i=5;i>=0;i--){
if(g[i]==a || g[i]==b || g[i]==c){
return g[i];
}
}
}
else if(t==-2){
int cnt=0;
for(int i=0;i<6;i++){
if(g[i]==a || g[i]==b || g[i]==c){
cnt++;
}
if(cnt==2){
return g[i];
}
}
}
else{
int cnt=0;
for(int i=0;i<6;i++){
if(g[i]==t){
cnt++;
}
if(cnt && (g[i]==a || g[i]==b || g[i]==c)){
return g[i];
}
}
return get(g,a,b,c,-1);
}
}
int fg(int a,int b,int c){
return getHeaviest(a+1,b+1,c+1)-1;
}
int fm(int a,int b,int c){
return getMedian(a+1,b+1,c+1)-1;
}
int fl(int a,int b,int c){
return getLightest(a+1,b+1,c+1)-1;
}
int nx(int a,int b,int c,int d){
return getNextLightest(a+1,b+1,c+1,d+1)-1;
}
int cal(vector<int>& x,int t,int i,int j,int k){
vector<int> b,c,d;
for(auto y:x){
auto h=z[x];
int a=get(h,i,j,k,t);
if(a==i){
b.push_back(h);
}
else if(a==j){
c.push_back(h);
}
else{
d.push_back(h);
}
}
if(dfs(b,s-1) && dfs(c,s-1) && dfs(d,s-1)){
return 1;
}
return 0;
}
int dfs(vector<int>& x,int s){
if(x.size()>po[s]){
return 1;
}
else if(mp.find(x)!=mp.end()){
if(mp[x][0]==-1){
return 0;
}
else{
return 1;
}
}
for(int i=0;i<4;i++){
for(int j=i+1;j<5;j++){
for(int k=j+1;k<6;k++){
for(int t=-3;t<6;t++){
if(t!=i && t!=j && t!=k){
if(cal(x,t,i,j,k)){
return mp[x]={i,j,k,t};
}
}
}
}
}
}
return mp[x]={-1,-1,-1,-1};
}
void init(int T){
vector<int> g(n);
iota(g.begin(),g.end(),0);
for(int i=0;i<720;i++){
z.push_back(g);
next_permutation(g.begin(),g.end());
}
vector<int> k(720);
iota(k.begin(),k.end(),0);
dfs(k,6);
}
void orderCoins(){
vector<int> g(720);
iota(g.begin(),g.end(),0);
while(g.size()>1){
auto h=mp[g];
vector<int> nw;
int y;
if(h[3]==-1){
y=fl(h[0],h[1],h[2]);
}
else if(h[3]==-2){
y=fm(h[0],h[1],h[2]);
}
else if(h[3]==-3){
y=fg(h[0],h[1],h[2]);
}
else{
y=nx(h[0],h[1],h[2],h[3]);
}
for(auto r:g){
if(get(z[r],h[0],h[1],h[2],h[3])==y){
nw.push_back(r);
}
}
g=nw;
}
answer(g);
}