제출 #303843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303843		jtnydv25	버섯 세기 (IOI20_mushrooms)	C++17	98.26 / 100	10 ms	504 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 10;
const int T = 3;
vector<int> ask[200];
int res[200][M];

void pre(){
	ask[1] = {0,3,1,4,2,5,6,7,8,9};
	res[1][0] = 2;
	res[1][1] = 3;
	ask[3] = {0,1,2,7,5,8,6};
	res[3][0] = 4;
	res[3][1] = 5;
	res[3][2] = 6;
	res[3][3] = 7;
	res[3][4] = 8;
	res[1][2] = 9;
	ask[9] = {5,0,6,1,7,2,8};
	res[9][0] = 10;
	ask[10] = {0,1,2,3};
	res[10][0] = 11;
	res[10][1] = 12;
	res[9][1] = 13;
	ask[13] = {0,1,2,5};
	res[13][0] = 14;
	res[13][1] = 15;
	res[9][2] = 16;
	ask[16] = {0,1,2,6};
	res[16][0] = 17;
	res[16][1] = 18;
	res[9][3] = 19;
	ask[19] = {0,1,2,5};
	res[19][0] = 20;
	res[19][1] = 21;
	res[9][4] = 22;
	res[9][5] = 23;
	ask[23] = {0,1,2,5};
	res[23][0] = 24;
	res[23][1] = 25;
	res[9][6] = 26;
	res[1][3] = 27;
	ask[27] = {0,5,1,6,2,7};
	res[27][0] = 28;
	ask[28] = {0,1,3,2,8};
	res[28][0] = 29;
	res[28][1] = 30;
	res[28][2] = 31;
	res[28][3] = 32;
	res[27][1] = 33;
	ask[33] = {0,1,2,3,4};
	res[33][0] = 34;
	res[33][1] = 35;
	res[33][2] = 36;
	res[27][2] = 37;
	ask[37] = {0,1,5,2,8};
	res[37][0] = 38;
	res[37][1] = 39;
	res[37][2] = 40;
	res[37][3] = 41;
	res[27][3] = 42;
	ask[42] = {0,1,3,2,6,4};
	res[42][0] = 43;
	res[42][1] = 44;
	res[42][2] = 45;
	res[42][4] = 46;
	res[27][4] = 47;
	ask[47] = {0,1,2,8};
	res[47][0] = 48;
	res[47][1] = 49;
	res[27][5] = 50;
	ask[50] = {0,1,2,3,4};
	res[50][0] = 51;
	res[50][1] = 52;
	res[50][2] = 53;
	res[1][4] = 54;
	ask[54] = {0,5,7,1,6,2,3,4};
	res[54][1] = 55;
	ask[55] = {0,1,2,3};
	res[55][0] = 56;
	res[55][1] = 57;
	res[54][2] = 58;
	ask[58] = {3,0,5,1,7,2,8};
	res[58][1] = 59;
	res[58][2] = 60;
	res[58][3] = 61;
	res[58][4] = 62;
	res[58][5] = 63;
	res[54][3] = 64;
	ask[64] = {5,0,1,6,2,4,8};
	res[64][1] = 65;
	res[64][2] = 66;
	res[64][3] = 67;
	res[64][4] = 68;
	res[54][4] = 69;
	ask[69] = {0,1,8,2,5,7};
	res[69][0] = 70;
	res[69][1] = 71;
	res[69][2] = 72;
	res[69][3] = 73;
	res[69][4] = 74;
	res[54][5] = 75;
	ask[75] = {0,7,1,8,2,5};
	res[75][1] = 76;
	res[75][2] = 77;
	res[75][3] = 78;
	res[75][4] = 79;
	res[75][5] = 80;
	res[54][6] = 81;
	ask[81] = {0,7,1,8,2,5};
	res[81][1] = 82;
	res[81][2] = 83;
	res[81][3] = 84;
	res[81][4] = 85;
	res[81][5] = 86;
	res[1][5] = 87;
	ask[87] = {3,9,5,7,0,4,1,8,2,6};
	res[87][1] = 88;
	res[87][2] = 89;
	ask[89] = {0,1,3,2,5,7};
	res[89][1] = 90;
	res[89][2] = 91;
	res[89][3] = 92;
	res[89][4] = 93;
	res[87][3] = 94;
	ask[94] = {0,1,5,2,7};
	res[94][0] = 95;
	res[94][1] = 96;
	res[94][2] = 97;
	res[94][3] = 98;
	res[87][4] = 99;
	ask[99] = {0,1,3,2,7,5};
	res[99][1] = 100;
	res[99][2] = 101;
	res[99][3] = 102;
	res[99][4] = 103;
	res[87][5] = 104;
	ask[104] = {0,1,2,7,3,5};
	res[104][0] = 105;
	res[104][1] = 106;
	res[104][2] = 107;
	res[104][3] = 108;
	res[87][6] = 109;
	ask[109] = {0,3,1,5,2,7};
	res[109][1] = 110;
	res[109][2] = 111;
	res[109][3] = 112;
	res[109][5] = 113;
	res[87][7] = 114;
	ask[114] = {0,1,2,3,5,7};
	res[114][0] = 115;
	res[114][1] = 116;
	res[114][2] = 117;
	res[114][3] = 118;
	res[87][8] = 119;
	res[1][6] = 120;
	ask[120] = {0,1,8,2,6,3,4,5};
	res[120][1] = 121;
	ask[121] = {0,1,6,2,7};
	res[121][0] = 122;
	res[121][1] = 123;
	res[121][2] = 124;
	res[121][3] = 125;
	res[120][2] = 126;
	ask[126] = {0,1,6,2,7};
	res[126][1] = 127;
	res[126][2] = 128;
	res[126][3] = 129;
	res[120][3] = 130;
	ask[130] = {0,1,4,2,7,3};
	res[130][1] = 131;
	res[130][2] = 132;
	res[130][3] = 133;
	res[130][4] = 134;
	res[120][4] = 135;
	ask[135] = {0,1,6,2,7};
	res[135][0] = 136;
	res[135][1] = 137;
	res[135][2] = 138;
	res[135][3] = 139;
	res[120][5] = 140;
	ask[140] = {0,1,3,2,7,6};
	res[140][1] = 141;
	res[140][2] = 142;
	res[140][3] = 143;
	res[140][4] = 144;
	res[120][6] = 145;
	res[1][7] = 146;
	ask[146] = {0,1,6,2,3,5,4,8,7};
	res[146][1] = 147;
	res[146][2] = 148;
	ask[148] = {0,1,2,8};
	res[148][0] = 149;
	res[148][1] = 150;
	res[146][3] = 151;
	ask[151] = {0,1,2,3};
	res[151][0] = 152;
	res[151][1] = 153;
	res[146][4] = 154;
	ask[154] = {0,1,2,8};
	res[154][0] = 155;
	res[154][1] = 156;
	res[146][5] = 157;
	ask[157] = {0,1,2,5};
	res[157][0] = 158;
	res[157][1] = 159;
	res[146][6] = 160;
	ask[160] = {0,1,2,8};
	res[160][0] = 161;
	res[160][1] = 162;
	res[146][7] = 163;
	res[1][8] = 164;
	ask[164] = {0,1,3,6,8,2,5,7};
	res[164][2] = 165;
	res[164][3] = 166;
	res[164][4] = 167;
	res[164][5] = 168;
	res[164][6] = 169;
	res[1][9] = 170;
}

int val[200005];
int get(int pos){
    return val[pos] = use_machine({0, pos});
}

void get(vector<int> positions){
	// assumption : positions[0], positions[1], positions[2] have the same value
	vector<int> states;
	for(int i = 0; i < (1 << M); i += (1 << T)) states.push_back(i);
	int node = 1;
	int asked = 0;
	while((int) states.size() > 1){
		assert(!ask[node].empty());
		vector<int> x;
		for(int u : ask[node]) x.push_back(positions[u]);
		int R = use_machine(x);
		asked++;
		vector<int> new_states;
		for(auto it : states){
			int r = 0;
			for(int j = 0; j + 1 < (int) ask[node].size(); j++) r += (it >> ask[node][j] & 1) != (it >> ask[node][j + 1] & 1);
			if(r == R) new_states.push_back(it);
		}
		node = res[node][R];
		assert(node != 0);
		states = new_states;
	}
	assert(asked <= 3);
	int mask = states[0];
	for(int i = 0; i < (int)positions.size(); i++) val[positions[i]] = (mask >> i & 1) ^ val[positions[0]];
}

const int K = 210;
int count_mushrooms(int N) {
	pre();
    int n = min(N, K);
	vector<vector<int>> w(2);
	w[0] = {0};
	int done = 0;
	if(n >= 5){
		for(int i = 1; i < 5; i++){
			get(i);
			w[val[i]].push_back(i);
			done = i;
		}
	}
	vector<int> f = (int)w[0].size() > (int) w[1].size() ? w[0] : w[1];
	f.resize(3);
    // int n = N;
    // for(int j = 1; j < N; j++) get(j);
    for(int i = done + 1; i < n; i += M - 3){
        int st = i, en = i + M - 2;
        if(en < n){
            vector<int> positions = f;
            for(int j = st; j <= en; j++) positions.push_back(j);
            get(positions);
        } else{
            for(int j = st; j < n; j++) get(j);
        }
    }
 
    int curr = n - accumulate(val, val + n, 0);
    if(n == N) return curr;
	vector<vector<int>> where(2);
    for(int i = 0; i < n; i++) where[val[i]].push_back(i);
	int i = n;
    while(i < N){
		int id = (int)where[1].size() > (int) where[0].size();
    	int R = where[id].size();
        int st = i, en = min(N - 1, i + R - 1);
        vector<int> positions;
        for(int j = 0; j <= en - st; j++){
            positions.push_back(where[id][j]);
            positions.push_back(st + j);
        }
        int V = use_machine(positions);
        if(V % 2 == 1){
			if(id == 1){
				where[0].push_back(positions.back());
				curr++;
			}
			else where[1].push_back(positions.back());
		} else{
			if(id == 0){
				where[0].push_back(positions.back());
				curr++;
			} else{
				where[1].push_back(positions.back());
			}
		}
        V /= 2;
        if(id == 1) curr += V;
        else curr += en - st - V;
		i = en + 1;
    }
    return curr;
}

• Subtask 1: 98.2609 / 100