Submission #531145

#	Time	Username	Problem	Language	Result	Execution time	Memory
531145		ColourAttila	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	9 ms	360 KiB

mushrooms

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

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
vector<int> knownA , knownB, ask;

int cnt;

int query1(vector<int> a) {
    int res = use_machine(a);

    if(res == 1)  {
        knownB.push_back(a.back());
    }
    else {
        knownA.push_back(a.back());
    }

    return res;
}

int query2(vector<int> a, bool type) {
    int res = use_machine(a);
    //cout << "type: " << type << endl;

    if(((res & 2) == 2) == type) {
        knownB.push_back(a[1]);
    }
    else {
        knownA.push_back(a[1]);
    }

    if(((res & 1) == 1) == type) {
        knownB.push_back(a.back());
    }
    else {
        knownA.push_back(a.back());
    }

    return res;
}

int query3(vector<int> a, bool type) {
    int res = use_machine(a);


    if(type) {
        cnt += (a.size() - res) / 2;
        if(!(res % 2)) knownA.push_back(a.back());
        else knownB.push_back(a.back());
    }
    else {
        cnt += (res + 1) / 2;
        if(res % 2) knownA.push_back(a.back());
        else knownB.push_back(a.back());
    }

    return res;
}

int count_mushrooms(int n){
    knownA.push_back(0);

    if (n<220) {
        for (int i=1; i<n; i++) {
            ask = {0, i};
            query1(ask);
        }
        return knownA.size();
    }


    ask = {0, 1};
    int curr = 1;

    // van legalabb 2
    int res = query1(ask);
    if(res == 1) {
        if(n == 2) return 1;
        ask[1] = 2;
        query1(ask);
        curr++;
    }

    if(n == curr+1) return knownA.size();

    int sq = sqrt(n)/2;
    //gyöknyi ugyanolyan keresese
    while((int)knownA.size() < sq && (int)knownB.size() < sq) {
        ask.clear();
        
        bool type;
        if(knownA.size() > 1) {
            ask = {knownA[0], ++curr, knownA[1], ++curr};
            type = 1;
        }
        else {
            ask = {knownB[0], ++curr, knownB[1], ++curr};
            type = 0;
        }

        query2(ask, type);
    }

    // megoldas
    cnt = knownA.size();
    while(curr < n-1) {
        ask.clear();
        bool type;
        
        if(knownA.size() > knownB.size()) {
            type = 1;
            for(int i = 0; i < (int)knownA.size(); i++) {
                ask.push_back(knownA[i]);
                ask.push_back(++curr);
                if(curr == n-1) break;
            }
        }
        else {
            type = 0;
            for(int i = 0; i < (int)knownB.size(); i++) {
                ask.push_back(knownB[i]);
                ask.push_back(++curr);
                if(curr == n-1) break;
            }
        }

        query3(ask, type);
    }

    return cnt;
}

• Subtask 1: 92.2449 / 100