Submission #989000

#	Time	Username	Problem	Language	Result	Execution time	Memory
989000		AdamGS	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	68 ms	1024 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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()
vector<int>OP[64];
int maska[64], V[64][9];
int solve(int v, vector<int>T) {
  if(OP[v].size()==0) return maska[v];
  vector<int>P;
  for(auto i : OP[v]) P.pb(T[i]);
  int x=use_machine(P);
  return solve(V[v][x], T);
}
int count_mushrooms(int n) {
OP[0]={0,1,5,2,6,3};
maska[0]=0;
V[0][0]=1;
OP[1]={0,4};
maska[1]=0;
V[1][0]=2;
OP[2]={};
maska[2]=31;
V[1][1]=3;
OP[3]={};
maska[3]=15;
V[1][2]=4;
OP[4]={};
maska[4]=0;
V[1][3]=5;
OP[5]={};
maska[5]=0;
V[1][4]=6;
OP[6]={};
maska[6]=0;
V[1][5]=7;
OP[7]={};
maska[7]=0;
V[1][6]=8;
OP[8]={};
maska[8]=0;
V[1][7]=9;
OP[9]={};
maska[9]=0;
V[1][8]=10;
OP[10]={};
maska[10]=0;
V[0][1]=11;
OP[11]={2,0,5,1,6,4};
maska[11]=0;
V[11][0]=12;
OP[12]={};
maska[12]=23;
V[11][1]=13;
OP[13]={};
maska[13]=7;
V[11][2]=14;
OP[14]={};
maska[14]=30;
V[11][3]=15;
OP[15]={};
maska[15]=14;
V[11][4]=16;
OP[16]={};
maska[16]=28;
V[11][5]=17;
OP[17]={};
maska[17]=12;
V[11][6]=18;
OP[18]={};
maska[18]=0;
V[11][7]=19;
OP[19]={};
maska[19]=0;
V[11][8]=20;
OP[20]={};
maska[20]=0;
V[0][2]=21;
OP[21]={1,5,0,6,4,7,3,2,8};
maska[21]=0;
V[21][0]=22;
OP[22]={};
maska[22]=0;
V[21][1]=23;
OP[23]={};
maska[23]=27;
V[21][2]=24;
OP[24]={};
maska[24]=29;
V[21][3]=25;
OP[25]={};
maska[25]=11;
V[21][4]=26;
OP[26]={};
maska[26]=13;
V[21][5]=27;
OP[27]={};
maska[27]=22;
V[21][6]=28;
OP[28]={};
maska[28]=20;
V[21][7]=29;
OP[29]={};
maska[29]=6;
V[21][8]=30;
OP[30]={};
maska[30]=4;
V[0][3]=31;
OP[31]={1,2,0,8,5,3,6,4,7};
maska[31]=0;
V[31][0]=32;
OP[32]={};
maska[32]=0;
V[31][1]=33;
OP[33]={};
maska[33]=24;
V[31][2]=34;
OP[34]={};
maska[34]=26;
V[31][3]=35;
OP[35]={};
maska[35]=8;
V[31][4]=36;
OP[36]={};
maska[36]=10;
V[31][5]=37;
OP[37]={};
maska[37]=21;
V[31][6]=38;
OP[38]={};
maska[38]=19;
V[31][7]=39;
OP[39]={};
maska[39]=5;
V[31][8]=40;
OP[40]={};
maska[40]=3;
V[0][4]=41;
OP[41]={2,1,0,5,3,6,4};
maska[41]=0;
V[41][0]=42;
OP[42]={};
maska[42]=0;
V[41][1]=43;
OP[43]={};
maska[43]=25;
V[41][2]=44;
OP[44]={};
maska[44]=9;
V[41][3]=45;
OP[45]={};
maska[45]=16;
V[41][4]=46;
OP[46]={};
maska[46]=0;
V[41][5]=47;
OP[47]={};
maska[47]=18;
V[41][6]=48;
OP[48]={};
maska[48]=2;
V[41][7]=49;
OP[49]={};
maska[49]=0;
V[41][8]=50;
OP[50]={};
maska[50]=0;
V[0][5]=51;
OP[51]={0,4};
maska[51]=0;
V[51][0]=52;
OP[52]={};
maska[52]=17;
V[51][1]=53;
OP[53]={};
maska[53]=1;
V[51][2]=54;
OP[54]={};
maska[54]=0;
V[51][3]=55;
OP[55]={};
maska[55]=0;
V[51][4]=56;
OP[56]={};
maska[56]=0;
V[51][5]=57;
OP[57]={};
maska[57]=0;
V[51][6]=58;
OP[58]={};
maska[58]=0;
V[51][7]=59;
OP[59]={};
maska[59]=0;
V[51][8]=60;
OP[60]={};
maska[60]=0;
V[0][6]=61;
OP[61]={};
maska[61]=0;
V[0][7]=62;
OP[62]={};
maska[62]=0;
V[0][8]=63;
OP[63]={};
maska[63]=0;
  vector<int>A, B;
  A.pb(0);
  int l=1;
  while(B.size()==0 && l<n) {
    int x=min(n-l, (int)A.size()+1);
    vector<int>T;
    int po=l;
    T.pb(l++);
    rep(i, x-1) {
      T.pb(A[i]);
      T.pb(l++);
    }
    if(x==1) T.pb(A[0]);
    int ko=l-1;
    int a=use_machine(T);
    if(a==0) {
      while(po<=ko) A.pb(po++);
      continue;
    }
    while(po<ko) {
      int sr=(po+ko)/2;
      T.clear();
      T.pb(po);
      rep(i, sr-po) {
        T.pb(A[i]);
        T.pb(po+i+1);
      }
      if(po==sr) T.pb(A[0]);
      a=use_machine(T);
      if(a==0) {
        while(po<=sr) A.pb(po++);
      } else ko=sr;
    }
    B.pb(po);
    l=po+1;
  }
  while(max(A.size(), B.size())<3 && l<n) {
    int x=use_machine({0, l});
    if(x==0) A.pb(l); else B.pb(l);
    ++l;
  }
  rep(i, n) {
    if(l+5>n) break;
    vector<int>T;
    rep(i, 5) T.pb(l++);
    if(A.size()>=3) {
      rep(i, 3) T.pb(A[i]);
      T.pb(B[0]);
    } else {
      rep(i, 3) T.pb(B[i]);
      T.pb(A[0]);
    }
    int x=solve(0, T);
    if(A.size()>=3) {
      rep(j, 5) if(x&(1<<j)) A.pb(T[j]); else B.pb(T[j]);
    } else {
      rep(j, 5) if(x&(1<<j)) B.pb(T[j]); else A.pb(T[j]);
    }
  }
  while(l<n) {
    int x=use_machine({0, l});
    if(x==0) A.pb(l); else B.pb(l);
    ++l;
  }
  return A.size();
}

• Subtask 1: 25 / 100