Submission #310292

#	Time	Username	Problem	Language	Result	Execution time	Memory
310292		nonthaphat	Counting Mushrooms (IOI20_mushrooms)	C++14	92.62 / 100	10 ms	516 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 sq = 175;
int use_machine(vector<int> x);
int count_mushrooms(int n){
    int ansA = 1, ansB = 0;
    vector<int> A, B;
    if(n <= sq){
        A.eb(0);
        for(int i=1;i<n;i++){
            vector<int> x;
            x.eb(0), x.eb(i);
            int result = use_machine(x);
            if(result == 0){
                A.eb(i);
                ansA++;
            }
            else{
                B.eb(i);
                ansB++;
            }
        }
    }
    else{
        A.eb(0);
        for(int i=1;i<3;i++){
            vector<int> x;
            x.eb(0), x.eb(i);
            int result = use_machine(x);
            if(result == 0){
                A.eb(i);
                ansA++;
            }
            else{
                B.eb(i);
                ansB++;
            }
        }

        if(sz(A) >= 2){
            for(int i=3;i<sq;i+=2){
                vector<int> x;
                x.eb(i), x.eb(A[0]), x.eb(i+1), x.eb(A[1]);
                int result = use_machine(x);
                if(result%2 == 0){
                    A.eb(i);
                    ansA++;
                }
                else{
                    B.eb(i);
                    ansB++;
                }
                if(result <= 1){
                    A.eb(i+1);
                    ansA++;
                }
                else{
                    B.eb(i+1);
                    ansB++;
                }
            }
        }
        else{
            for(int i=3;i<sq;i+=2){
                vector<int> x;
                x.eb(i), x.eb(B[0]), x.eb(i+1), x.eb(B[1]);
                int result = use_machine(x);
                if(result%2 == 0){
                    B.eb(i);
                    ansB++;
                }
                else{
                    A.eb(i);
                    ansA++;
                }
                if(result <= 1){
                    B.eb(i+1);
                    ansB++;
                }
                else{
                    A.eb(i+1);
                    ansA++;
                }
            }
        }
        int cur = sq;
        while(cur != n){
            if(sz(A) > sz(B)){
                int cnt = min(n-cur, sz(A));
                vector<int> x;
                for(int i=0;i<cnt;i++){
                    x.eb(cur+i), x.eb(A[i]);
                }
                int result = use_machine(x);
                int tmp = cur;
                cur += cnt;
                if(result%2 == 0){
                    A.eb(tmp);
                    ansA++;
                }
                else{
                    B.eb(tmp);
                    ansB++;
                }
                ansA += (cnt-1)-result/2;
                ansB += result/2;
            }
            else{
                int cnt = min(n-cur, sz(B));
                vector<int> x;
                for(int i=0;i<cnt;i++){
                    x.eb(cur+i), x.eb(B[i]);
                }
                int result = use_machine(x);
                int tmp = cur;
                cur += cnt;
                if(result%2 == 0){
                    B.eb(tmp);
                    ansB++;
                }
                else{
                    A.eb(tmp);
                    ansA++;
                }
                ansA += result/2;
                ansB += (cnt-1)-result/2;
            }
        }
    }
    return ansA;
}

• Subtask 1: 92.623 / 100