Submission #720712

#	Time	Username	Problem	Language	Result	Execution time	Memory
720712		nguyentunglam	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	11 ms	464 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int a[20010], order[20010];
vector<int> A, B;
int usemachine(vector<int> ask) {
    vector<int> nxt;
    for(int &j : ask) nxt.push_back(order[j]);
    return use_machine(nxt);
}
int count_mushrooms(int n) {
    for(int i = 1; i < n; i++) order[i] = i;
    random_shuffle(order + 1, order + n);
    if (n == 2) return 1 + (usemachine({0, 1}) == 0);

    a[1] = usemachine({0, 1});
    a[2] = usemachine({0, 2});
    int x, y, type = 0;
    if (a[1] + a[2] == 2) {
        type = 1;
        x = 1; y = 2;
    }
    else {
        type = 0;
        if (a[1] == 0) x = 0, y = 1;
        else x = 0, y = 2;
    }

    int T = min(280, n);
    int ed = 2;
    for(int i = 4; i < T; i += 2) {
        int tmp = usemachine({x, i - 1, y, i});

        if (tmp / 2 > 0) a[i - 1] = type ^ 1;
        else a[i - 1] = type;

        if (tmp % 2) a[i] = type ^ 1;
        else a[i] = type;
        ed = i;
    }

    for(int i = 0; i <= ed; i++) {
        if (!a[i]) A.push_back(i);
        else B.push_back(i);
    }
    bool ok = 0;
    int tmp = 0;
    if (A.size() < B.size()) swap(A, B), ok = 1;
    int sz = A.size(), cnt = 0;
    for(int i = ed + 1; i < n; i += sz) {
        vector<int> ask;
        for(int j = i; j < n && j < i + sz; j++) {
            ask.push_back(A[j - i]);
            ask.push_back(j);
            cnt++;
        }
        tmp += (usemachine(ask) + 1) / 2;
    }
    if (!ok) return A.size() + cnt - tmp;
    return B.size() + tmp;
}

• Subtask 1: 80.427 / 100