Submission #1302461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302461		regulardude6	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	396 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static int n;
static vector<ll> val;
static vector<int> bought;

static vector<vector<int>> unk;
static vector<ll> sumunk;

static inline ll guess_min_first(ll S, int k){
    __int128 two = (__int128)2 * S;
    ll q = (ll)(two / k);
    ll z = (q + 1 - k) / 2;
    if(z < 1) z = 1;
    return z;
}

static void add_eq(ll M){
    auto res = transaction(M);
    for(int x: res.first) bought[x]++;
    int y = res.first[0];
    ll S = M - res.second;
    for(int x: res.first){
        if(val[x] != -1) S -= val[x];
        else unk[y].push_back(x);
    }
    sumunk[y] = S;
}

static void remove_last(){
    int last = n - 1;
    ll v = val[last];
    for(int i=0;i<n;i++){
        if(unk[i].empty()) continue;
        auto &dq = unk[i];
        if(!dq.empty() && dq.back() == last){
            dq.pop_back();
            sumunk[i] -= v;
        }
    }
    n--;
}

static void solve_from(int x){
    if(x >= n-1) return;

    add_eq(val[x] - 1);

    int start = x + 1;
    while(true){
        int lst = -1;
        for(int i=start;i<n;i++){
            if(val[i]==-1 && !unk[i].empty()) lst = i;
        }
        if(lst == -1) break;

        if((int)unk[lst].size() == 1){
            int id = unk[lst][0];
            val[id] = sumunk[lst];
            unk[lst].clear();
            if(id < n-1) solve_from(id);
            while(n>=2 && val[n-1] != -1) remove_last();
        }else{
            ll p = guess_min_first(sumunk[lst], (int)unk[lst].size());
            if(p >= val[0]) p = val[0] - 1;
            if(p < 1) p = 1;
            add_eq(p);
        }
    }
}

void buy_souvenirs(int N, long long P0){
    n = N;
    val.assign(n, -1);
    bought.assign(n, 0);
    unk.assign(n, {});
    sumunk.assign(n, -1);

    val[0] = P0;

    solve_from(0);
    while(n>=2 && val[n-1] != -1) remove_last();

    for(int i=1;i<N;i++){
        while(bought[i] < i){
            auto res = transaction(val[i]);
            for(int x: res.first) bought[x]++;
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33