Submission #1203662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203662		LucaLucaM	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	468 KiB

mushrooms

#include "mushrooms.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>

std::mt19937 rng(123);

int calcK(int n) {
  int K = 1;
  int best = 1e9;
  for (int k = 1; k <= n; k++) {
    if (3 * k / 2 + (n - 3 * k / 2) / k < best) {
      best = 3 * k / 2 + (n - 3 * k / 2) / k;
      K = k;
    } 
  }
  return K;
}

int count_mushrooms(int n) {
  std::vector<int> A, B;
  A.push_back(0);
  int cntA = 0;
  for (int i = 1; i < n;) {
    int addI = std::max((int) A.size(), (int) B.size());
    if (A.size() > B.size()) { // xAyAzA
      std::vector<int> query;
      for (int k = 0; k < (int) A.size() && i + k < n; k++) {
        query.push_back(i + k);
        query.push_back(A[k]);
      }
      int aux = use_machine(query);
      // aux % 2 imi spune despre prima valoare daca e B(1) sau A(0)
      // hai sa iau un ex
      // bAaAaAbAbAaA (are lungime 12)
      // fiecare a imi da +0
      // fiecare b imi da +2, mai putin primul care imi da +1
      // 2 * 2 + 1 = 5 de la b uri
      // primesc rezultatul 5
      // eu zic ca am 12 / 2 - 5 / 2 - 1 = 6 - 2 - 1 = 4 - 1 = 3 a uri (sper ca e bine)
      if (aux % 2 == 0) {
        A.push_back(i);
      } else {
        B.push_back(i);
      }

      aux -= aux % 2; // practic am sters primul element
  
      int sz = (int) query.size() - 2;
      // x * (sz / 2)
      // bs * 2 == aux
      // as + bs = sz / 2
      // 2 * as + aux == sz 
      // as = (sz - aux) / 2 
      // asta pare bine
      cntA += sz / 2 - aux / 2;
    } else { // xByBzB
      std::vector<int> query;
      for (int k = 0; k < (int) B.size() && i + k < n; k++) {
        query.push_back(i + k);
        query.push_back(B[k]);
      }
      int aux = use_machine(query);
      if (aux % 2 == 0) {
        B.push_back(i);
      } else {
        A.push_back(i);
      }  

      aux -= aux % 2; // practic am sters primul element
      cntA += aux / 2;
    }
    i += addI;
  }
  return cntA + (int) A.size();
}

• Subtask 1: 80.7143 / 100