Submission #423238

#	Time	Username	Problem	Language	Result	Execution time	Memory
423238		xyz	Counting Mushrooms (IOI20_mushrooms)	C++17	75.59 / 100	16 ms	344 KiB

mushrooms

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

int m = 50;

int count_mushrooms(int n){
    vector<int> A, B;
    A = {0};
    int go = 2 * m + 5;
    for(int i = 1; i < min(n, go); i ++){
        vector<int> ask = {0, i};
        int x = use_machine(ask);
        if(!x)
            A.push_back(i);
        else
            B.push_back(i);
    }
//    for(int x : A)
//        cout << x << " ";
//    cout << endl;
//    for(int x : B)
//        cout << x << " ";
//    cout << endl;
    int result = A.size(), pos = go;
    while(pos < n){
        m = max((int)A.size(), (int)B.size()) - 1;
        if(A.size() >= B.size()){
            vector<int> ask;
            if(pos + m < n)
                ask.push_back(pos + m);
            ask.push_back(A[0]);
            int cur = 1;
            for(int j = pos; j < min(n, pos + m); j ++){
                ask.push_back(j);
                ask.push_back(A[cur]);
                ++ cur;
            }
//            cout << "-query1" << endl;
//            cout << ask.size() << endl;
//            for(int e : ask)
//                cout << e << " ";
//            cout << endl;
            int x = use_machine(ask), y = ask.size();
//            cout << "reply = " << x << endl;
            if(pos + m < n){
                -- y;
                if(x % 2 == 1){
                    B.push_back(pos + m);
                    -- x;
                }else{
                    A.push_back(pos + m);
                    ++ result;
                }
            }
            result += ((y - 1) - x) / 2;
            pos += m + 1;
        }else{
            vector<int> ask;
            if(pos + m < n)
                ask.push_back(pos + m);
            ask.push_back(B[0]);
            int cur = 1;
            for(int j = pos; j < min(n, pos + m); j ++){
                ask.push_back(j);
                ask.push_back(B[cur]);
                ++ cur;
            }
//            cout << "-query2" << endl;
//            cout << ask.size() << endl;
//            for(int e : ask)
//                cout << e << " ";
//            cout << endl;
            int x = use_machine(ask);
//            cout << "reply = " << x << endl;
            if(pos + m < n){
                if(x % 2 == 1){
                    A.push_back(pos + m);
                    ++ result;
                    -- x;
                }else{
                    B.push_back(pos + m);
                }
            }
            result += x / 2;
            pos += m + 1;
        }
    }
    return result;
}

//23
//0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0
//answer : 17

• Subtask 1: 75.5853 / 100