Submission #940792

#	Time	Username	Problem	Language	Result	Execution time	Memory
940792		AdamGS	Scales (IOI15_scales)	C++17	71.43 / 100	395 ms	2956 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int INF=1e9+7;
struct node {
  int typ=-1, A, B, C, D;
  int nxta, nxtb, nxtc;
  vector<int>P;
};
node puste;
vector<node>V;
int solve(vector<vector<int>>&T, int ind, int dep);
int get_hev(vector<int>&T, int A, int B, int C) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  return P[2].nd;
}
int get_lig(vector<int>&T, int A, int B, int C) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  return P[0].nd;
}
int get_med(vector<int>&T, int A, int B, int C) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  return P[1].nd;
}
int get_nxt(vector<int>&T, int A, int B, int C, int D) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  for(auto i : P) if(i.st>T[D]) return i.nd;
  return P[0].nd;
}
int rob(vector<vector<int>>&T, int ind, int dep, int typ, int A, int B, int C, int D) {
  vector<vector<int>>X, Y, Z;
  for(auto i : T) {
    int p;
    if(typ==0) p=get_hev(i, A, B, C);
    if(typ==1) p=get_lig(i, A, B, C);
    if(typ==2) p=get_med(i, A, B, C);
    if(typ==3) p=get_nxt(i, A, B, C, D);
    if(p==A) X.pb(i);
    if(p==B) Y.pb(i);
    if(p==C) Z.pb(i);
  }
  V[ind].typ=typ;
  V[ind].A=A;
  V[ind].B=B;
  V[ind].C=C;
  V[ind].D=D;
  int ans=0;
  if(X.size()) {
    V[ind].nxta=V.size();
    V.pb(puste);
    ans=max(ans, solve(X, V[ind].nxta, dep+1)+1);
  }
  if(Y.size()) {
    V[ind].nxtb=V.size();
    V.pb(puste);
    ans=max(ans, solve(Y, V[ind].nxtb, dep+1)+1);
  }
  if(Z.size()) {
    V[ind].nxtc=V.size();
    V.pb(puste);
    ans=max(ans, solve(Z, V[ind].nxtc, dep+1)+1);
  }
  return ans;
}
int solve(vector<vector<int>>&T, int ind, int dep) {
  if(T.size()==1) V[ind].P=T[0];
  if(T.size()<=1) return 0;
  int mi=INF;
  rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
    int x=0, y=0, z=0;
    for(auto i : T) {
      int p=get_hev(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    mi=min(mi, max(max(x, y), z));
    x=y=z=0;
    for(auto i : T) {
      int p=get_lig(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    mi=min(mi, max(max(x, y), z));
    x=y=z=0;
    for(auto i : T) {
      int p=get_med(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    mi=min(mi, max(max(x, y), z));
    rep(D, 6) if(A!=D && B!=D && C!=D) {
      x=y=z=0;
      for(auto i : T) {
        int p=get_nxt(i, A, B, C, D);
        if(p==A) ++x;
        if(p==B) ++y;
        if(p==C) ++z;
      }
      mi=min(mi, max(max(x, y), z));
    }
  }
  rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
    int x=0, y=0, z=0;
    for(auto i : T) {
      int p=get_hev(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    if(max(max(x, y), z)==mi) {
      int q=rob(T, ind, dep, 0, A, B, C, 0);
      if(q+dep<=6) return q;
    }
    x=y=z=0;
    for(auto i : T) {
      int p=get_lig(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    if(max(max(x, y), z)==mi) {
      int q=rob(T, ind, dep, 1, A, B, C, 0);
      if(q+dep<=6) return q;
    }
    x=y=z=0;
    for(auto i : T) {
      int p=get_med(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    if(max(max(x, y), z)==mi) {
      int q=rob(T, ind, dep, 2, A, B, C, 0);
      if(q+dep<=6) return q;
    }
    rep(D, 6) if(A!=D && B!=D && C!=D) {
      x=y=z=0;
      for(auto i : T) {
        int p=get_nxt(i, A, B, C, D);
        if(p==A) ++x;
        if(p==B) ++y;
        if(p==C) ++z;
      }
      if(max(max(x, y), z)==mi) {
        int q=rob(T, ind, dep, 3, A, B, C, D);
        if(q+dep<=6) return q;
      }
    }
  }
  return 0;
}
void init(int T) {
  V.pb(puste);
  vector<vector<int>>P;
  vector<int>X;
  rep(i, 6) X.pb(i);
  do P.pb(X); while(next_permutation(all(X)));
  solve(P, 0, 0);
}
void zejdz(int x) {
  if(V[x].P.size()==6) {
    int ans[6];
    rep(i, 6) ans[V[x].P[i]]=i+1;
    answer(ans);
    return;
  }
  int p;
  if(V[x].typ==0) p=getHeaviest(V[x].A+1, V[x].B+1, V[x].C+1);
  if(V[x].typ==1) p=getLightest(V[x].A+1, V[x].B+1, V[x].C+1);
  if(V[x].typ==2) p=getMedian(V[x].A+1, V[x].B+1, V[x].C+1);
  if(V[x].typ==3) p=getNextLightest(V[x].A+1, V[x].B+1, V[x].C+1, V[x].D+1);
  if(p==V[x].A+1) zejdz(V[x].nxta);
  if(p==V[x].B+1) zejdz(V[x].nxtb);
  if(p==V[x].C+1) zejdz(V[x].nxtc);
}
void orderCoins() {
  zejdz(0);
}

Compilation message (stderr)

scales.cpp: In function 'int rob(std::vector<std::vector<int> >&, int, int, int, int, int, int, int)':
scales.cpp:70:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   70 |     V[ind].nxta=V.size();
      |                 ~~~~~~^~
scales.cpp:75:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |     V[ind].nxtb=V.size();
      |                 ~~~~~~^~
scales.cpp:80:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   80 |     V[ind].nxtc=V.size();
      |                 ~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:176:15: warning: unused parameter 'T' [-Wunused-parameter]
  176 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void zejdz(int)':
scales.cpp:196:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  196 |   if(p==V[x].A+1) zejdz(V[x].nxta);
      |   ^~
scales.cpp: In function 'int rob(std::vector<std::vector<int> >&, int, int, int, int, int, int, int)':
scales.cpp:61:5: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     if(p==C) Z.pb(i);
      |     ^~

• Subtask 1: 71.428571 / 100