제출 #605115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605115		Mher	버섯 세기 (IOI20_mushrooms)	C++14	31.22 / 100	18 ms	456 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>

using namespace std;

const int M = 121;

/*
5
0 1 1 0 1
*/


int count_mushrooms(int n) {
	vector<int> cl(n, -1);
	cl[0] = 1;
	if (n == 2)
    {
        return 2 - use_machine({0, 1});
    }
    cl[1] = 1 - use_machine({0, 1});
    cl[2] = 1 - use_machine({0, 2});
    bool t;
    int x, y;
    if (cl[0] == cl[1])
    {
        t = true;
        x = 0;
        y = 1;
    }
    else if (cl[0] == cl[2])
    {
        t = true;
        x = 0;
        y = 2;
    }
    else
    {
        t = false;
        x = 1;
        y = 2;
    }
    for (int i = 3; i < min(n - 1, M); i += 2)
    {
        int res = use_machine({x, i, y, i + 1});
        if (res == 0)
        {
            cl[i] = cl[i + 1] = t;
        }
        else if (res == 1)
        {
            cl[i] = t;
            cl[i + 1] = !t;
        }
        else if (res == 2)
        {
            cl[i] = !t;
            cl[i + 1] = t;
        }
        else
        {
            cl[i] = cl[i + 1] = !t;
        }
    }
    if (n < M && n % 2 == 0)
    {
        cl[n - 1] = 1 - use_machine({0, n - 1});
    }
    int ans = 0;
    if (n < M)
    {
        for (int i = 0; i < n; i++)
            ans += cl[i];
        return ans;
    }
    int as = 0;
    for (int i = 0; i < M; i++)
    {
        as += cl[i];
    }
    ans += as;
    bool cs = as > M / 2;
    vector<int> ch;
    for (int i = 0; i < M; i++)
    {
        if (cl[i] == cs)
        {
            //cout << i << endl;
            ch.push_back(i);
        }
    }
    if (ch.size() % 2 == 1)
    {
        ch.pop_back();
    }
    int len = ch.size() / 2;
    for (int i = M; i < n; i += len)
    {
        vector<int> q;
        for (int j = 0; j < min(len, n - i); j++)
        {
            q.push_back(ch[j * 2]);
            q.push_back(i + j);
            q.push_back(ch[j * 2 + 1]);
        }
        int res = use_machine(q) / 2;
        ans += !cs ? res : min(len, n - i) - res;
        //cout << '-' << i << ' ' << res << ' ' << ans << endl;
    }
    return ans;
}

• Subtask 1: 31.2155 / 100