Submission #1287596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287596		takoshanava	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	14 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;

long long a[105], f[105], sz = 0;

void solve(long long i){
    pair<vector<int>,long long> rs = transaction(i);
    for(int i:rs.fs) f[i]++;
    while(rs.fs.back() >= sz){
        rs.sc += a[rs.fs.back()];
        rs.fs.pop_back();
    }

    while(rs.fs.size() > 1){
        solve((i - rs.sc) / rs.fs.size());
        while(rs.fs.back() >= sz){
            rs.sc += a[rs.fs.back()];
            rs.fs.pop_back();
        }
    }

    a[rs.fs[0]] = i - rs.sc;
    if(sz != rs.fs[0] + 1) solve(a[rs.fs[0]] - 1);
    sz = rs.fs[0];
}
void buy_souvenirs(int n, long long P0){
    sz = n;
    a[0] = P0;
    solve(P0 - 1);
    for(int i = 1; i < n; i++) while(f[i] < i){
        transaction(a[i]);
        f[i]++;
    }
    return;
}

• 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