Submission #1052529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052529		nightfal	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1077 ms	596 KiB

biscuits

#include <cassert>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define ll long long

template <typename T> void print(T elem) {cout << elem << " ";}
template <typename T> void print(vector<T> &v) {for(auto elem: v) print(elem); cout << endl;}

void arrange(ll x, vector<ll> &a) {
    int k=a.size();
	for(int i=0; i<k-1; i++)
		if (a[i] > x+1) {
			ll excess = (a[i]-x)/2;
			a[i] -= 2*excess;
			a[i+1] += excess;
		}
	return;
}

int possible(ll n, ll x, vector<ll> a) {
	int k = a.size();
    // cout << "n:" << n << endl;

    ll m = n;
	for(int i=0; i<k && m>0; i++) {
		bool one = m%2; m >>= 1;
		if (a[i] > x+1) {
			ll excess = (a[i]-x)/2;
			a[i] -= 2*excess;
			a[i+1] += excess;
		}        
		if (one) {if (a[i]<x) return 0;}
    	else if (i<k-1) {a[i+1] += a[i]/2; a[i]=0;}
        // cout << "i:" << i << ", a: "; print(a);
	}
    if (m>0) return 0;
    else return 1;
}
ll subtask2(vector<ll> a) {
    int k=a.size();
    ll prev = 0, curr = 1;
    for(int i=0; i<k; i++) {
        switch(a[i]) {
            case 0: curr += prev; prev = 0; break;
            case 1: curr *=2; break;
            case 2: prev += curr; curr *=2; 
        }
        // cout << "i:" << i << " prev:" << prev << " curr:" << curr << endl;
    }
    return curr;
}
ll subtask1(ll x, vector<ll> a) {
	ll cnt = 0;
	for(int i=0; i<=100'000; i++) {
		cnt += possible(i,x,a);
    }
    return cnt;
}
void cal(int l, ll x, vector<ll> a, vector<ll> &ans){
    if (a[l]>=x) {ans[l] = l==0? 2:ans[l-1]*2; return;}
    ll diff = x-a[l];
    ans[l] = ans[l-1];

    for(int i=l-1; i>=0; i--) {
        diff *= 2;
        if (diff < 0) return;
        if (diff <= a[i]) {ans[l] += i==0? 1:ans[i-1]; diff += x-a[i];}
        else {diff -=a[i];}
    }
    return;
}
ll fulltask(ll x, vector<ll> a) {
    int k= a.size();
    vector<ll> ans(k);
    for(int i=0; i<k; i++) {
        cal(i,x,a,ans);
    }
    // print(ans);
    return ans[k-1];
}
ll count_tastiness(ll x, std::vector<ll> a) {
    a.resize(60,0);
	arrange(x,a);
    // return fulltask(x,a);
    if (x==1) return subtask2(a);
    return subtask1(x, a);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23