Submission #605098

#	Time	Username	Problem	Language	Result	Execution time	Memory
605098		Sam_a17	Counting Mushrooms (IOI20_mushrooms)	C++14	79.02 / 100	13 ms	1256 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_mushrooms2(int n) {
	// std::vector<int> m;
	// for (int i = 0; i < n; i++)
		// m.push_back(i);
	// int c1 = use_machine(m);
	// m = {0, 1};
	// int c2 = use_machine(m);
	// return c1+c2;
 
  // int curr = 1;
  // vector<int> a{0}, b;
  // int s = 1;
  // for(int i = 1; i + 1 < n; i += 2) {
  //   vector<int> ask{i, 0, i + 1};
  //   int c1 = use_machine(ask);
  //   s += 2 - c1;
  // }
 
  // if(n % 2 == 0) {
  //   vector<int> ask{0, n - 1};
  //   int c1 = use_machine(ask);
  //   s += 1 - c1;
  // }
 
  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 = 120;
  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 >= lim || kBx >= lim) {
      start = i + 1;
      break;
    }
  }
 
  if(start == -1) {
    return kAx;
  }
 
  if(kAx >= lim || !kBx) {
    int i = start;
    for(; i + kAx <= n; i += kAx) {
      vector<int> qry;
      for(int j = i, k = 0; j < i + kAx; j++, k++) {
        qry.push_back(zeroes[k]);
        qry.push_back(j);
      }
 
      int s = use_machine(qry);
 
      int ci = 0;
      if(s % 2 == 1) {
        s--, ci++;
      } 
      answ += (kAx - ci) - (s / 2);
    }
 
    vector<int> qry;
    int ki = 0;
    for(int j = i; j < n; j++, ki++) {
      qry.push_back(zeroes[ki]);
      qry.push_back(j);
    }
 
    if(!qry.empty()) {
      int s = use_machine(qry), ci = 0;
      if(s % 2 == 1) {
        s--, ci++;
      } 
      answ += (sz(qry) / 2 - ci) - (s / 2);
    }
    return answ + kAx;
  } else {
    int i = start;
    for(; i + kBx <= n; i += kBx) {
      vector<int> qry;
      for(int j = i, k = 0; j < i + kBx; j++, k++) {
        qry.push_back(ones[k]);
        qry.push_back(j);
      }
 
      // pr(qry);
      int s = use_machine(qry);
 
      if(s % 2 == 1) {
        s--, answ++;
      }
      answ += (s / 2);
      // dbg(answ)
    }
 
    vector<int> qry;
    int ki = 0;
    for(int j = i; j < n; j++, ki++) {
      qry.push_back(ones[ki]);
      qry.push_back(j);
    }
 
 
    if(!qry.empty()) {
      int s = use_machine(qry);
      if(s % 2 == 1) {
        s--, answ++;
      }
      answ += (s / 2);
    }
    return answ + kAx;
  }
}

int count_mushrooms(int n) {
	// std::vector<int> m;
	// for (int i = 0; i < n; i++)
		// m.push_back(i);
	// int c1 = use_machine(m);
	// m = {0, 1};
	// int c2 = use_machine(m);
	// return c1+c2;
 
  // int curr = 1;
  // vector<int> a{0}, b;
  // int s = 1;
  // for(int i = 1; i + 1 < n; i += 2) {
  //   vector<int> ask{i, 0, i + 1};
  //   int c1 = use_machine(ask);
  //   s += 2 - c1;
  // }
 
  // if(n % 2 == 0) {
  //   vector<int> ask{0, n - 1};
  //   int c1 = use_machine(ask);
  //   s += 1 - c1;
  // }
 
  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 = 120;
  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) {
      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;
    }
  } 

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

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms2(int)':
mushrooms.cpp:60:25: warning: unused variable 'cnt' [-Wunused-variable]
   60 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                         ^~~
mushrooms.cpp:60:34: warning: unused variable 'qn' [-Wunused-variable]
   60 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                                  ^~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:186:25: warning: unused variable 'cnt' [-Wunused-variable]
  186 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                         ^~~
mushrooms.cpp:186:34: warning: unused variable 'qn' [-Wunused-variable]
  186 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                                  ^~

• Subtask 1: 79.021 / 100