Submission #313995

#	Time	Username	Problem	Language	Result	Execution time	Memory
313995		nonthaphat	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	9 ms	392 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;

typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<ll, pii> plpii;
typedef pair<db, db> pdd;
typedef pair<ld, ld> pldd;

typedef vector<int> vi;
typedef vector<pii> vii;
 
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FOR2(i, a, b) for(int i=(a);i<=(b);++i)
#define ROF(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define ROF2(i, a, b) for(int i=(b);i>=(a);--i)
#define GO(i, x) for(auto &i : x)

#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define eb emplace_back
#define pf push_front
#define pb push_back
#define lb lower_bound
#define up upper_bound

template<typename T> inline bool min2(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool max2(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int P1 = 999983, P2 = 999979;
const ld PI = acos((ld)-1);
const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const ll INF = 1e18;
const int N = 1e6;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int M = 100;
int use_machine(vector<int> x);

void partV1(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while(count_A < 2 && count_B < 2){
        vector<int> x;
        x.push_back(0);
        x.push_back(i);
        int result = use_machine(x);
        if(result == 0){
            A.push_back(i);
            count_A++;
        }
        else{
            B.push_back(i);
            count_B++;
        }
        i++;
    }
}
void partV2(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while((count_A < 3 || count_B < 2) && (count_A < 2 || count_B < 3) && count_A < M && count_B < M){
        bool sw = 0;
        if(count_A < count_B){
            sw = 1;
            swap(A, B);
            swap(count_A, count_B);
        }
        vector<int> x;
        x.push_back(i);
        x.push_back(A[0]);
        x.push_back(i+1);
        x.push_back(A[1]);
        int result = use_machine(x);
        switch(result){
            case 0: 
                A.push_back(i);
                A.push_back(i+1);
                count_A += 2;
                break;
            case 1:
                B.push_back(i);
                A.push_back(i+1);
                count_A++;
                count_B++;
                break;
            case 2:
                A.push_back(i);
                B.push_back(i+1);
                count_A++;
                count_B++;
                break;
            default:
                B.push_back(i);
                B.push_back(i+1);
                count_B += 2;
        }
        if(sw){
            swap(A, B);
            swap(count_A, count_B);
        }
        i += 2;
    }
}
void partV3(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while(count_A < M && count_B < M){
        bool sw = 0;
        if(count_A < count_B){
            sw = 1;
            swap(A, B);
            swap(count_A, count_B);
        }
        vector<int> x;
        x.push_back(i);
        x.push_back(A[0]);
        x.push_back(i+1);
        x.push_back(A[1]);
        x.push_back(i+2);
        x.push_back(A[2]);

        int result = use_machine(x);
        if(result%2 == 0){
            A.push_back(i);
            count_A++;
        }
        else{
            B.push_back(i);
            count_B++;
        }
        if(result-result%2 == 0){
            A.push_back(i+1);
            A.push_back(i+2);
            count_A += 2;
            i += 3;
        }
        else if(result-result%2 == 4){
            B.push_back(i+1);
            B.push_back(i+2);
            count_B += 2;
            i += 3;
        }
        else{
            vector<int> x;
            x.push_back(B[0]);
            x.push_back(i+1);
            x.push_back(B[1]);
            x.push_back(A[0]);
            x.push_back(i+2);
            x.push_back(A[1]);
            x.push_back(i+3);
            x.push_back(A[2]);
            x.push_back(i+4);

            int result = use_machine(x);
            switch(result){
                case 1:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    A.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 3;
                    count_B += 1;
                    break;
                case 2:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    A.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 3:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    B.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 4:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    B.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 1;
                    count_B += 3;
                    break;
                case 5:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    A.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 3;
                    count_B += 1;
                    break;
                case 6:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    A.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 7:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    B.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                default:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    B.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 1;
                    count_B += 3;
            }
            i += 5;
        }

        if(sw){
            swap(A, B);
            swap(count_A, count_B);
        }
    }
}
void partV4(int &i, int &n, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
    while(i < n){
        bool sw = 0;
        if(A.size() < B.size()){
            sw = 1;
            swap(A, B);
            swap(count_A, count_B);
        }

        vector<int> x;
        int L = min((int)A.size(), n-i);
        for(int j=0;j<L;j++){
            x.push_back(i+j);
            x.push_back(A[j]);
        }

        int result = use_machine(x);
        if(result%2 == 0){
            A.push_back(i);
            count_A++;
        }
        else{
            B.push_back(i);
            count_B++;
        }
        count_B += result/2;
        count_A += (L-1) - result/2;

        if(sw){
            swap(A, B);
            swap(count_A, count_B);
        }
        i += L;
    }
}
int count_mushrooms(int n){
    int count_A = 1, count_B = 0;
    int i = 1;
    vector<int> A, B;
    A.push_back(0);
    if(n <= 226){
        while(i < n){
            vector<int> x;
            x.push_back(0);
            x.push_back(i);
            int result = use_machine(x);
            if(result == 0){
                A.push_back(i);
                count_A++;
            }
            else{
                B.push_back(i);
                count_B++;
            }
            i++;
        }
        return count_A;
    }
    partV1(i, A, B, count_A, count_B);
    partV2(i, A, B, count_A, count_B);
    partV3(i, A, B, count_A, count_B);
    partV4(i, n, A, B, count_A, count_B);
    return count_A;
}

• Subtask 1: 100 / 100