Submission #1306106

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

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
vector<ll>p;
vector<int>b;
int N,ft;
void buy_souvenirs(int n, ll P0) {
    queue<pair<int,ll>>q;
    N=n,p.assign(N,-1),b.assign(N,0),p[0]=P0,q.push({1,P0});
    while(q.size()) {
        auto[idx,up]=q.front();q.pop();
        if(idx>=N||p[idx]^-1)continue;
        auto[it,ch]=transaction(up-1);
        for(int t:it)b[t]++;
        vector<int>pd;
        ll lo=ch;
        for(int i=it.size()-1,t;i;i--)t=it[i],p[t]^-1?pd.push_back(t),0:lo+=p[t];
        if(pd.size()) {
            ll rm=up-1-lo,av=rm/(pd.size()+1)+1;
            for(int t:pd)q.push({t,av});
            q.push({idx,up});
            continue;
        }
        ft=it[0],p[ft]=up-1-lo,q.push({ft+1,p[ft]});
    }
    for(int i=1;i<N;i++) {
        while(b[i]<i) {
            auto[it,ch]=transaction(p[i]);
            for(int t:it)b[t]++;
        }
    }
}

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