제출 #1326985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326985		SmuggingSpun	버섯 세기 (IOI20_mushrooms)	C++20	92.62 / 100	3 ms	520 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e4 + 5;
const int SIZE = 85;
int a[lim];
vector<int>pos[2];
int count_mushrooms(int n){
  pos[0].push_back(a[0] = 0);
  if(n <= 553){
    int ans = 1;
    for(int i = 2; i < n; i += 2){
      ans += 2 - use_machine({i - 1, 0, i});
    }
    if(~n & 1){
      ans += 1 - use_machine({0, n - 1});
    }
    return ans;
  }
  for(int i = 1; i < 3; i++){
    pos[a[i] = use_machine({0, i})].push_back(i);
  }
  auto calc = [&] (int i, int near, int z){
    pos[a[i] = near ^ z].push_back(i);
  };
  int cur = 3;
  while(max(pos[0].size(), pos[1].size()) < SIZE){
    int color = pos[0].size() > 1 ? 0 : 1, z = use_machine({cur, pos[color][0], cur + 1, pos[color][1]});
    calc(cur, color, z & 1);
    calc(cur + 1, color, z >> 1);
    cur += 2;
  }
  int ans = pos[0].size();
  while(cur < n){
    int color = pos[0].size() > pos[1].size() ? 0 : 1;
    vector<int>ask;
    for(int i = 0; i < pos[color].size() && cur < n; i++){
      ask.push_back(cur++);
      ask.push_back(pos[color][i]);
    }
    int z = use_machine(ask);
    if(color == 0){
      ans += (int(ask.size()) >> 1) - ((z + 1) >> 1);
    }
    else{
      ans += (z + 1) >> 1;
    }
    calc(ask[0], color, z & 1);
  }
  return ans;
}

• Subtask 1: 92.623 / 100