oj.uz

Submission #989034

# Submission time Handle Problem Language Result Execution time Memory
989034 2024-05-27T10:17:05 Z AdamGS Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 8 ms 788 KB 
#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()
const int K=40;
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);
  vector<int>perm(n);
  rep(i, n-1) perm[i+1]=i+1;
  mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  rep(i, n-1) swap(perm[i+1], perm[rng()%(i+1)+1]);
  int l=1, ans=0;
  while(B.size()==0 && l<n) {
    int x=min(n-l, (int)A.size());
    vector<int>T;
    int po=l;
    rep(i, x) {
      T.pb(perm[l++]);
      T.pb(A[i]);
    }
    int ko=l-1;
    int a=use_machine(T);
    if(a==0) {
      while(po<=ko) A.pb(perm[po++]);
      continue;
    }
    if(a%2==0) A.pb(perm[po++]); else {
      B.pb(perm[po++]);
      ans+=ko-po+1-a/2;
      continue;
    }
    while(po<ko) {
      int sr=(po+ko)/2;
      T.clear();
      T.pb(perm[po]);
      rep(i, sr-po) {
        T.pb(A[i]);
        T.pb(perm[po+i+1]);
      }
      if(po==sr) T.pb(A[0]);
      a=use_machine(T);
      if(a==0) {
        while(po<=sr) A.pb(perm[po++]);
      } else ko=sr;
    }
    B.pb(perm[po]);
    //a-=2;
    l=po+1;
    //ans+=ko-po-a/2;
  }
  while(max(A.size(), B.size())<3 && l<n) {
    if(A.size()>=B.size()) {
      int p=min(n-l, (int)A.size());
      vector<int>T;
      rep(i, p) {
        T.pb(A[i]);
        T.pb(perm[l]);
        ++l;
      }
      int x=use_machine(T);
      if(x%2==0) A.pb(perm[l-1]); else B.pb(perm[l-1]);
      ans+=p-1-x/2;
    } else {
      int p=min(n-l, (int)B.size());
      vector<int>T;
      rep(i, p) {
        T.pb(B[i]);
        T.pb(perm[l]);
        ++l;
      }
      int x=use_machine(T);
      if(x%2==0) B.pb(perm[l-1]); else A.pb(perm[l-1]);
      ans+=x/2;
    }
  }
  rep(i, K) {
    if(l+5>n) break;
    vector<int>T;
    rep(i, 5) T.pb(perm[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) {
    if(A.size()>=B.size()) {
      int p=min(n-l, (int)A.size());
      vector<int>T;
      rep(i, p) {
        T.pb(A[i]);
        T.pb(perm[l]);
        ++l;
      }
      int x=use_machine(T);
      if(x%2==0) A.pb(perm[l-1]); else B.pb(perm[l-1]);
      ans+=p-1-x/2;
    } else {
      int p=min(n-l, (int)B.size());
      vector<int>T;
      rep(i, p) {
        T.pb(B[i]);
        T.pb(perm[l]);
        ++l;
      }
      int x=use_machine(T);
      if(x%2==0) B.pb(perm[l-1]); else A.pb(perm[l-1]);
      ans+=x/2;
    }
  }
  ans+=A.size();
  return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 5 ms 532 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 4 ms 344 KB Output is correct
17 Correct 3 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Correct 4 ms 344 KB Output is correct
21 Correct 5 ms 600 KB Output is correct
22 Correct 4 ms 344 KB Output is correct
23 Correct 5 ms 344 KB Output is correct
24 Correct 3 ms 344 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 4 ms 344 KB Output is correct
27 Correct 4 ms 536 KB Output is correct
28 Correct 4 ms 344 KB Output is correct
29 Correct 4 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 7 ms 344 KB Output is correct
32 Correct 8 ms 344 KB Output is correct
33 Correct 6 ms 344 KB Output is correct
34 Correct 6 ms 344 KB Output is correct
35 Correct 6 ms 344 KB Output is correct
36 Correct 4 ms 344 KB Output is correct
37 Correct 6 ms 344 KB Output is correct
38 Correct 6 ms 344 KB Output is correct
39 Correct 4 ms 788 KB Output is correct
40 Correct 5 ms 532 KB Output is correct
41 Correct 6 ms 528 KB Output is correct
42 Correct 5 ms 344 KB Output is correct
43 Correct 5 ms 344 KB Output is correct
44 Correct 4 ms 540 KB Output is correct
45 Correct 5 ms 532 KB Output is correct
46 Correct 5 ms 532 KB Output is correct
47 Correct 5 ms 408 KB Output is correct
48 Correct 5 ms 344 KB Output is correct
49 Correct 4 ms 788 KB Output is correct
50 Correct 4 ms 548 KB Output is correct
51 Correct 5 ms 344 KB Output is correct
52 Correct 5 ms 544 KB Output is correct
53 Correct 3 ms 344 KB Output is correct
54 Correct 5 ms 344 KB Output is correct
55 Correct 5 ms 344 KB Output is correct
56 Correct 7 ms 348 KB Output is correct
57 Correct 5 ms 544 KB Output is correct
58 Correct 4 ms 352 KB Output is correct
59 Correct 5 ms 784 KB Output is correct
60 Correct 4 ms 536 KB Output is correct
61 Correct 5 ms 536 KB Output is correct
62 Correct 0 ms 352 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 352 KB Output is correct
66 Correct 0 ms 352 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 0 ms 356 KB Output is correct
69 Correct 0 ms 352 KB Output is correct
70 Correct 1 ms 348 KB Output is correct
71 Correct 0 ms 352 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 0 ms 352 KB Output is correct
75 Correct 0 ms 344 KB Output is correct
76 Correct 1 ms 352 KB Output is correct
77 Correct 1 ms 348 KB Output is correct
78 Correct 0 ms 352 KB Output is correct
79 Correct 1 ms 348 KB Output is correct
80 Correct 0 ms 344 KB Output is correct
81 Correct 0 ms 344 KB Output is correct
82 Correct 0 ms 344 KB Output is correct
83 Correct 1 ms 344 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 0 ms 344 KB Output is correct
86 Correct 0 ms 344 KB Output is correct
87 Correct 0 ms 344 KB Output is correct
88 Correct 1 ms 344 KB Output is correct
89 Correct 1 ms 344 KB Output is correct
90 Correct 0 ms 344 KB Output is correct
91 Correct 1 ms 344 KB Output is correct