Submission #313442

#	Time	Username	Problem	Language	Result	Execution time	Memory
313442		nonthaphat	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	0 ms	256 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);
int count_mushrooms(int n){
    int count_A = 0, count_B = 0;
    vector<int> A, B;
    A.push_back(0);

    int k = 1;
    if(n <= M+10){
        while(sz(A) + sz(B) < n){
            vector<int> x;
            x.push_back(0);
            x.push_back(k);
            int result = use_machine(x);
            if(result == 0){
                A.push_back(k);
                count_A++;
            }
            else{
                B.push_back(k);
                count_B++;
            }
            k++;
        }
    }
    else{
        while(sz(A) < 2 && sz(B) < 2 && (sz(A) < M && sz(B) < M)){
            vector<int> x;
            x.push_back(0);
            x.push_back(k);
            int result = use_machine(x);
            if(result == 0) A.push_back(k);
            else B.push_back(k);
            k++;
        }
        while(((sz(A) < 3 || sz(B) < 2) && (sz(B) < 3 || sz(A) < 2)) && (sz(A) < M && sz(B) < M)){
            vector<int> x;
            bool sw = 0;
            if(sz(A) < sz(B)){
                sw = 1;
                swap(A, B);
            }
            x.push_back(k);
            x.push_back(A[0]);
            x.push_back(k+1);
            x.push_back(A[1]);
            int result = use_machine(x);
            if(result%2 == 0) A.push_back(k);
            else B.push_back(k);
            if(result/2 == 0) A.push_back(k+1);
            else B.push_back(k+1);
            k += 2;
            if(sw) swap(A, B);
        }
        while((sz(A) < M && sz(B) < M)){
            vector<int> x;
            bool sw = 0;
            if(sz(A) < sz(B)){
                sw = 1;
                swap(A, B);
            }
            x.push_back(k);
            x.push_back(A[0]);
            x.push_back(k+1);
            x.push_back(A[1]);
            x.push_back(k+2);
            x.push_back(A[2]);
            int result = use_machine(x);
            if(result%2 == 0) A.push_back(k);
            else B.push_back(k);
            if(result/2 == 0) A.push_back(k+1), A.push_back(k+2), k += 3;
            else if(result/2 == 2) B.push_back(k+1), B.push_back(k+2), k += 3;
            else{
                x.clear();
                x.push_back(B[0]);
                x.push_back(k+1);
                x.push_back(B[1]);
                x.push_back(A[0]);
                x.push_back(k+2);
                x.push_back(A[1]);
                x.push_back(k+3);
                x.push_back(A[2]);
                x.push_back(k+4);
 
                int result = use_machine(x);
                if(result%2 == 1) A.push_back(k+4);
                else B.push_back(k+4);
 
                if(result >= 5){
                    A.push_back(k+1);
                    B.push_back(k+2);
                    if(result < 7) A.push_back(k+3);
                    else B.push_back(k+3);
                }
                else{
                    A.push_back(k+2);
                    B.push_back(k+1);
                    if(result < 3) A.push_back(k+3);
                    else B.push_back(k+3);
                }
                k += 5;
            }
            if(sw) swap(A, B);
        }
 
        count_A = sz(A);
        count_B = sz(B);
        while(count_A + count_B < n){
            vector<int> x;
            bool sw = 0;
            if(sz(A) < sz(B)){
                sw = 1;
                swap(A, B);
                swap(count_A, count_B);
            }
 
            int le = min(sz(A), n-k);
            for(int i=0;i<le;i++){
                x.push_back(k+i);
                x.push_back(A[i]);
            }
 
            int result = use_machine(x);
            if(result%2 == 0) A.push_back(k), count_A++;
            else B.push_back(k), count_B++;
            count_A += (le-1) - result/2;
            count_B += result/2;
            k += le;
 
            if(sw){
                swap(A, B);
                swap(count_A, count_B);
            }
        }
    }
    return count_A;
}

• Subtask 1: 0 / 100