Submission #1217789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217789		lighton	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 ms	464 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 = 80;

vector<vector<bool> > S[8]; int Q[8],F[8];
void calc(){
    S[0] = {{true}};
    Q[0] = 1;
    F[0] = 1;
    forf(k,1,7){
        F[k] = 2*F[k-1] + Q[k-1]-1;
        Q[k] = 2*Q[k-1];
        S[k].resize((1<<k),vector<bool>(F[k],false));
        forf(j,F[k-1],2*F[k-1]-1) S[k][0][j] = true;
        forf(i,0,Q[k-1]-2){
            forf(j,0,F[k-1]-1) S[k][2*i+1][j] = S[k-1][i][j], S[k][2*i+1][F[k-1]+j] = S[k-1][i][j];
            forf(j,0,F[k-1]-1) S[k][2*i+2][j] = S[k-1][i][j], S[k][2*i+2][F[k-1]+j] = !S[k-1][i][j];
            S[k][2*i+2][2*F[k-1]+i] = true;
        }
        forf(j,0,F[k]-1) S[k][Q[k]-1][j] = true;
    }
}
vector<int> eval(int k, vector<int> sum){
    //assert(sz(sum) == Q[k]);
    if(k==0) return sum;
    vector<int> l(F[k-1]),r(F[k-1]),res(F[k]);
    int ra = sum[0];
    int la = sum.back()-sum[0];
    forf(i,0,Q[k-1]-2){
        if(sum[2*i+1]%2 != sum[2*i+2]%2) res[2*F[k-1]+i] = 1, sum[2*i+2]--, la--;
        sum[2*i+2] -= ra;
        l[i] = (sum[2*i+1]+sum[2*i+2])/2;
        r[i] = (sum[2*i+1]-sum[2*i+2])/2;
    }
    l[Q[k-1]-1] = la, r[Q[k-1]-1] = ra;
    vector<int> resl = eval(k-1,l), resr = eval(k-1,r);
    forf(i,0,F[k-1]-1) res[i] = resl[i], res[F[k-1]+i] = resr[i];
    return res;
}

vector<int> A,B;
deque<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_front(), q.pb(A[0]);
    if(sz(A) >= 2 && sz(C)) q.pb(C.front()), sec = C.front(), C.pop_front(), 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 go10(){
    int f = 0;
    if(sz(A) < sz(B)) f=1, swap(A,B);
    int k = 0;
    while(k+1<=7 && F[k+1]+1 <= sz(A)) k++;
    vector<int> sum;
    forf(i,0,Q[k]-1){
        vector<int> q;
        forf(j,0,F[k]-1){
            q.pb(A[j]);
            if(S[k][i][j]) q.pb(C[j]);
        }
        q.pb(A[F[k]]);
        q.pb(C.back());
        int res = use_machine(q);
        if(res%2) B.pb(C.back()), C.pop_back();
        sum.pb(res/2);
    }
    auto e = eval(k,sum);

    forf(i,0,F[k]-1){
        if(e[i]) B.pb(C[i]);
        else A.pb(C[i]);
    }
    forf(i,0,F[k]-1) C.pop_front();
    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_front(), 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) {
    calc();

    A.pb(0);
	forf(i,1,n-1) C.pb(i);
    if(n <= 400){
        while(sz(C)) go1();
    }
    else{
        while(sz(C) && (sz(A) < 2 && sz(B) < 2)) go1();
        while(sz(C) && (sz(A) < K && sz(B) < K)) go10();
        while(sz(C)) go2();
    }
	return sz(A)+ans;
}

• Subtask 1: 0 / 100