제출 #1326997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326997		SmuggingSpun	Counting Mushrooms (IOI20_mushrooms)	C++20	100 / 100	3 ms	516 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e4 + 5;
const int SIZE = 100;
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);
  };
  if(pos[0].size() > 1){
    int z = use_machine({3, pos[0][0], 4, pos[0][1]});
    calc(3, 0, z & 1);
    calc(4, 0, z >> 1);
  }
  else{
    int z = use_machine({3, pos[1][0], 4, pos[1][1]});
    calc(3, 1, z & 1);
    calc(4, 1, z >> 1);
  }
  int cur = 5;
  while(max(pos[0].size(), pos[1].size()) < SIZE){
    int color = pos[0].size() > 2 ? 0 : 1, z = use_machine({cur, pos[color][0], cur + 1, pos[color][1], cur + 2, pos[color][2]});
    calc(cur, color, z & 1);
    if((z >> 1) != 1){
      calc(cur + 1, color, z >> 2);
      calc(cur + 2, a[cur + 1], 0);
      cur += 3;
    }
    else if(pos[color ^ 1].size() > 1){
      calc(cur + 4, color, (z = use_machine({pos[color ^ 1][0], cur + 1, pos[color ^ 1][1], pos[color][0], cur + 2, pos[color][1], cur + 3, pos[color][2], cur + 4}) - 1) & 1);
      calc(cur + 3, color, (z >> 1) & 1);
      calc(cur + 2, color, z >> 2);
      calc(cur + 1, a[cur + 2], 1);
      cur += 5;
    }
    else{
      calc(cur + 1, 0, use_machine({0, cur + 1}));
      calc(cur + 2, a[cur + 1], 1);
      cur += 3;
    }
  }
  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: 100 / 100