oj.uz

Submission #1016905

# Submission time Handle Problem Language Result Execution time Memory
1016905 2024-07-08T15:13:24 Z shenfe1 Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 6 ms 868 KB 
#include <bits/stdc++.h>
#include "mushrooms.h"

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(s) (int)s.size()
#define lb lower_bound

using namespace std;

const int MAX=2e4+100;
const int inf=1e9;

int count_mushrooms(int n){
  vector<int> a={0},b;
  int pos=1;
  int C=105;
  while(pos<n&&max(sz(a),sz(b))<C){
    if(pos+4<n&&min(sz(a),sz(b))>1&&max(sz(a),sz(b))>2){
      if(sz(a)>sz(b)){
        int cnt=use_machine({a[0],pos,a[1],pos+1,a[2],pos+2});
        if(cnt&1)b.pb(pos+2);
        else a.pb(pos+2);
        cnt/=2;
        if(cnt==0){
          a.pb(pos),a.pb(pos+1);
          pos+=3;
        }
        else if(cnt==1){
          int cnt1=use_machine({b[0],pos,b[1],a[0],pos+1,a[1],pos+3,a[2],pos+4})-1;
          if(cnt1&1)b.pb(pos+4);
          else a.pb(pos+4);
          if(cnt1&2)b.pb(pos+3);
          else a.pb(pos+3);
          if(cnt1&4){
            a.pb(pos);
            b.pb(pos+1);
          }
          else{
            a.pb(pos+1);
            b.pb(pos);
          }
          pos+=5;
        }
        else{
          assert(cnt==2);
          b.pb(pos),b.pb(pos+1);
          pos+=3;
        }
      }
      else{
        int cnt=use_machine({b[0],pos,b[1],pos+1,b[2],pos+2});
        if(cnt&1)a.pb(pos+2);
        else b.pb(pos+2);
        cnt/=2;
        if(cnt==0){
          b.pb(pos),b.pb(pos+1);
          pos+=3;
        }
        else if(cnt==1){
          int cnt1=use_machine({a[0],pos,a[1],b[0],pos+1,b[1],pos+3,b[2],pos+4})-1;
          if(cnt1&1)a.pb(pos+4);
          else b.pb(pos+4);
          if(cnt1&2)a.pb(pos+3);
          else b.pb(pos+3);
          if(cnt1&4){
            a.pb(pos+1);
            b.pb(pos);
          }
          else{
            a.pb(pos);
            b.pb(pos+1);
          }
          pos+=5;
        }
        else{
          a.pb(pos),a.pb(pos+1);
          pos+=3;
        }
      }
    }
    else if(pos+1<n&&max(sz(a),sz(b))>1){
      if(sz(a)>=2){
        int cnt=use_machine({pos,a[0],pos+1,a[1]});
        if(cnt&1){
          b.pb(pos);
        }
        else{
          a.pb(pos);
        }
        cnt/=2;
        if(cnt&1){
          b.pb(pos+1);
        }
        else{
          a.pb(pos+1);
        }
      }
      else{
        int cnt=use_machine({pos,b[0],pos+1,b[1]});
        if(cnt&1){
          a.pb(pos);
        }
        else{
          b.pb(pos);
        }
        cnt/=2;
        if(cnt&1){
          a.pb(pos+1);
        }
        else{
          b.pb(pos+1);
        }
      }
      pos+=2;
    }
    else{
      if(use_machine({pos,0}))b.pb(pos);
      else a.pb(pos);
      pos++;
    }
  }
  sort(all(a));
  int ans=sz(a);
  // cout<<ans<<"\n";
  for(int i=pos;i<n;){
    if(sz(a)>sz(b)){
      int R=i+sz(a);
      vector<int> vect;
      for(int j=i;j<min(n,i+sz(a)-1);j++){
        vect.pb(a[j-i]);
        vect.pb(j);
      }
      vect.pb(a.back());
      if(i+sz(a)-1<n)vect.pb(i+sz(a)-1);
      int cnt=use_machine(vect);
      ans+=min(n,i+sz(a)-1)-i-cnt/2;
      if(i+sz(a)-1<n){
        if(cnt%2==1)b.pb(i+sz(a)-1);
        else a.pb(i+sz(a)-1),ans++;
      }
      i=R;
    }
    else{
      int R=i+sz(b);
      vector<int> vect;
      for(int j=i;j<min(n,i+sz(b)-1);j++){
        vect.pb(b[j-i]);
        vect.pb(j);
      }
      vect.pb(b.back());
      if(i+sz(b)-1<n)vect.pb(i+sz(b)-1);
      int cnt=use_machine(vect);
      ans+=cnt/2;
      if(i+sz(b)-1<n){
        if(cnt%2==1)a.pb(i+sz(b)-1),ans++;
        else b.pb(i+sz(b)-1);
      }
      i=R;
    }
  }
  return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 600 KB Output is correct
8 Correct 3 ms 452 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 3 ms 452 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 3 ms 344 KB Output is correct
19 Correct 3 ms 344 KB Output is correct
20 Correct 6 ms 344 KB Output is correct
21 Correct 3 ms 344 KB Output is correct
22 Correct 6 ms 344 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 3 ms 344 KB Output is correct
25 Correct 5 ms 344 KB Output is correct
26 Correct 4 ms 344 KB Output is correct
27 Correct 3 ms 344 KB Output is correct
28 Correct 5 ms 452 KB Output is correct
29 Correct 3 ms 344 KB Output is correct
30 Correct 3 ms 344 KB Output is correct
31 Correct 3 ms 344 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Correct 3 ms 452 KB Output is correct
34 Correct 6 ms 344 KB Output is correct
35 Correct 3 ms 600 KB Output is correct
36 Correct 3 ms 344 KB Output is correct
37 Correct 5 ms 868 KB Output is correct
38 Correct 3 ms 344 KB Output is correct
39 Correct 3 ms 344 KB Output is correct
40 Correct 4 ms 448 KB Output is correct
41 Correct 3 ms 344 KB Output is correct
42 Correct 3 ms 344 KB Output is correct
43 Correct 4 ms 344 KB Output is correct
44 Correct 6 ms 600 KB Output is correct
45 Correct 6 ms 344 KB Output is correct
46 Correct 3 ms 600 KB Output is correct
47 Correct 3 ms 344 KB Output is correct
48 Correct 3 ms 344 KB Output is correct
49 Correct 3 ms 344 KB Output is correct
50 Correct 3 ms 452 KB Output is correct
51 Correct 3 ms 344 KB Output is correct
52 Correct 4 ms 600 KB Output is correct
53 Correct 6 ms 704 KB Output is correct
54 Correct 3 ms 344 KB Output is correct
55 Correct 5 ms 460 KB Output is correct
56 Correct 3 ms 340 KB Output is correct
57 Correct 3 ms 456 KB Output is correct
58 Correct 3 ms 344 KB Output is correct
59 Correct 3 ms 344 KB Output is correct
60 Correct 3 ms 344 KB Output is correct
61 Correct 4 ms 344 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 0 ms 344 KB Output is correct
64 Correct 0 ms 344 KB Output is correct
65 Correct 0 ms 344 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 0 ms 344 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 0 ms 344 KB Output is correct
72 Correct 0 ms 344 KB Output is correct
73 Correct 0 ms 344 KB Output is correct
74 Correct 1 ms 344 KB Output is correct
75 Correct 0 ms 344 KB Output is correct
76 Correct 0 ms 344 KB Output is correct
77 Correct 0 ms 344 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 0 ms 344 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 0 ms 344 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 0 ms 596 KB Output is correct
86 Correct 0 ms 344 KB Output is correct
87 Correct 0 ms 344 KB Output is correct
88 Correct 0 ms 344 KB Output is correct
89 Correct 0 ms 344 KB Output is correct
90 Correct 0 ms 344 KB Output is correct
91 Correct 0 ms 344 KB Output is correct