제출 #305324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305324		abeker	Counting Mushrooms (IOI20_mushrooms)	C++17	79.86 / 100	9 ms	384 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;

typedef pair <int, int> pii;

int count_mushrooms(int N) {
  int ans = 1;
  int root = sqrt(N);
  vector <vector <int>> by_type(2);
  auto larger = [&]() -> pii {
    vector <pii> tmp(2);
    for (int i = 0; i < 2; i++)
      tmp[i] = {by_type[i].size(), i};
    return max(tmp[0], tmp[1]);
  };
  pii big;
  int pos = 1;
  by_type[0].push_back(0);
  while (pos < N) {
    big = larger();
    if (big.first > root)
      break;
    if (big.first >= 3 && pos < N - 1) {
      int curr = use_machine({by_type[big.second][0], pos, by_type[big.second][1], by_type[big.second][2], pos + 1});
      int x = curr / 2 ^ big.second;
      int y = curr % 2 ^ big.second;
      by_type[x].push_back(pos);
      by_type[y].push_back(pos + 1);
      ans += !x;
      ans += !y;
      pos += 2;
    }
    else {
      int curr = use_machine({0, pos});
      by_type[curr].push_back(pos);
      ans += !curr;
      pos++;
    }
  }
  for (int i = pos; i < N; i += big.first - 1) {
    vector <int> sequence = {by_type[big.second][0]};
    for (int j = i; j < min(N, i + big.first - 1); j++) {
      sequence.push_back(j);
      sequence.push_back(by_type[big.second][j - i + 1]);
    }
    int curr = use_machine(sequence) / 2;
    ans += big.second ? curr : (int)sequence.size() / 2 - curr;
  }
  return ans;
}

• Subtask 1: 79.8587 / 100