Submission #605161

#	Time	Username	Problem	Language	Result	Execution time	Memory
605161		Sam_a17	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	1 ms	208 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define ld long double
#define ll long long
 
// #include "mushrooms.h"
int use_machine(vector<int> m);
 
void pr(vector<int>& a) {
  cerr << "arr" << " ";
  for(auto i: a) {
    cerr << i << " "; 
  } cerr << endl;
}
 
 
// #include "mushrooms.h"
int use_machine(vector<int> m);

int count_mushrooms(int n) {
  set<int> st;
  for(int i = 0; i < n; i++) {
    st.insert(i);
  }
 
  int answ = 0;
  int kAx = 1, kBx = 0, cnt = 0, qn = 0;
  int lim = 160;
  vector<int> ones, zeroes{0};
  int start = -1;

  for(int i = 1; i < n; i++) {
    vector<int> aski{0, i};
    int s = use_machine(aski);
    if(s == 1) {
      ones.push_back(i);
      kBx++;
    } else {
      zeroes.push_back(i);
      kAx++;
    }
 
    if(kAx >= 2 || kBx >= 2) {
      start = i + 1;
      break;
    }
  }
 
  if(start == -1) {
    return kAx;
  }

  if(kAx >= 2) {
    for(int i = start; i + 1 < n; i += 2) {
      vector<int> ask{0, i, zeroes.back(), i + 1};
      int s = use_machine(ask);
      
      if(s == 0) {
        zeroes.push_back(i);
        zeroes.push_back(i + 1);
      } else if(s == 1) {
        zeroes.push_back(i);
        ones.push_back(i + 1);
      } else if(s == 2) {
        ones.push_back(i);
        zeroes.push_back(i + 1);
      } else {
        ones.push_back(i);
        ones.push_back(i + 1);
      }
      
      //
      kAx = sz(zeroes), kBx = sz(ones);

      if(kAx >= lim || kBx >= lim) {
        start = i + 2;
        break;
      }

      start += 2;
    }
  } else  {
    for(int i = start; i + 1 < n; i += 2) {
      vector<int> ask{ones.front(), i, ones.back(), i + 1};
      int s = use_machine(ask);
      
      if(s == 0) {
        ones.push_back(i);
        ones.push_back(i + 1);
      } else if(s == 1) {
        ones.push_back(i);
        zeroes.push_back(i + 1);
      } else if(s == 2) {
        zeroes.push_back(i);
        ones.push_back(i + 1);
      } else {
        zeroes.push_back(i);
        zeroes.push_back(i + 1);
      }
      
      //
      kAx = sz(zeroes), kBx = sz(ones);
 
      if(kAx >= lim || kBx >= lim) {
        start = i + 2;
        break;
      }

      start += 2;
    }
  }

  // pr(zeroes);
  // pr(ones);
  // dbg(answ)
  int countt = 0;
  while(start < n) {
    kAx = sz(zeroes), kBx = sz(ones);

    if(kAx > kBx) {
      // dbg("alo")
      vector<int> qry;
      for(int j = start, k = 0; j < min(n, start + kAx); j++, k++) {
        qry.push_back(zeroes[k]);
        qry.push_back(j);
      }
 
      if(!qry.empty()) {
        int s = use_machine(qry);
        // dbg(s)
  
        int ci = 0;
        bool flag = false;
        if(s % 2 == 1) {
          s--, ci++;
          ones.push_back(qry.back());
        } else {
          countt++;
          zeroes.push_back(qry.back());
        }

        // dbg(s)
        // dbg(sz(qry))
        answ += (sz(qry) / 2 - ci) - (s / 2);
        // dbg(answ)
        pr(zeroes);
      }
    } else {
      vector<int> qry;
      for(int j = start, k = 0; j < min(n, start + kBx); j++, k++) {
        qry.push_back(ones[k]);
        qry.push_back(j);
      }
 
      if(!qry.empty()) {
        int s = use_machine(qry);
  
        int ci = 0;

        if(s % 2 == 1) {
          s--, countt++;
          zeroes.push_back(qry.back());
        } else {
          ones.push_back(qry.back());
        }
        answ += (s / 2);
      }
    }

    // dbg(answ)
    // pr(zeroes);
    // pr(ones);
    start += max(kAx, kBx);
  } 
  
  // dbg(countt)
  
  return answ + sz(zeroes) - countt;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:142:14: warning: unused variable 'flag' [-Wunused-variable]
  142 |         bool flag = false;
      |              ^~~~
mushrooms.cpp:167:13: warning: unused variable 'ci' [-Wunused-variable]
  167 |         int ci = 0;
      |             ^~
mushrooms.cpp:36:25: warning: unused variable 'cnt' [-Wunused-variable]
   36 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                         ^~~
mushrooms.cpp:36:34: warning: unused variable 'qn' [-Wunused-variable]
   36 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                                  ^~

• Subtask 1: 0 / 100