Submission #1214888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214888		lighton	Counting Mushrooms (IOI20_mushrooms)	C++20	25 / 100	27 ms	716 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;


int K = 87;

vector<vector<int> > S[10];
void calc(){
    S[0] = {{0}};

}

vector<int> A,B;
queue<int> C;
int ans = 0;

void go1(){
    vector<int> q;
    int f = 0;
    if(sz(A) < sz(B)) f=1, swap(A,B);
    int fst = -1, sec = -1;
    q.pb(C.front()), fst=C.front(), C.pop(), q.pb(A[0]);
    if(sz(A) >= 2 && sz(C)) q.pb(C.front()), sec = C.front(), C.pop(), q.pb(A[1]);
    int res = use_machine(q);

    if(res & 1) B.pb(fst);
    else A.pb(fst);
    if(sec!=-1) {
        if (res & 2) B.pb(sec);
        else A.pb(sec);
    }
    if(f) swap(A,B);
}

void go2(){
    vector<int> q;
    int f = 0;
    if(sz(A) < sz(B)) f=1, swap(A,B);
    int fst = C.front();
    int cnt = -1;
    for(auto i : A){
        if(sz(C)) q.pb(C.front()), C.pop(), cnt++;
        q.pb(i);
    }
    int res = use_machine(q);

    if(f == 0){
        if(res % 2) B.pb(fst);
        else A.pb(fst);
        ans += cnt - res/2;
    }
    else{
        if(res % 2) B.pb(fst);
        else A.pb(fst);
        ans += res/2;
    }
    if(f) swap(A,B);
}


int count_mushrooms(int n) {
    A.pb(0);
	forf(i,1,n-1) C.push(i);
    while(sz(C) && (sz(A) < K || sz(B) < K)) go1();
    while(sz(C)) go2();

	return sz(A)+ans;
}

• Subtask 1: 25 / 100