Submission #1306108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306108		exoworldgd	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	13 ms	404 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;
void buy_souvenirs(int N, ll P0) {
    ll p[N];int b[N],pd[N],ft;
    for(int i=0;i<N;i++)p[i]=-1,b[i]=0;
    p[0]=P0;
    queue<pair<int,ll>>q;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]++;
        int ps=0;
        ll lo=ch;
        for(int i=it.size()-1,t;i;i--)t=it[i],p[t]^-1?pd[ps++]=t,0:lo+=p[t];
        if(ps) {
            ll rm=up-1-lo,av=rm/(ps+1)+1;
            for(int i=0;i<ps;i++)q.push({pd[i],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