Submission #1254109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254109		garam1732	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	12 ms	412 KiB

souvenirs

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*1;
const ll MOD = 1e9+7;
const ll INF = 1e9+10;

pair<vector<int>, ll> res;
int cnt[110];
ll arr[110];

void dnc(int s, int e, ll tot) {
    ll sum = tot - res.ss;
    auto v = res.ff; int sz = v.size();

    if(s == e) {
        arr[s] = sum;
        return;
    }

    if(sz == 1) {
        arr[s] = sum;
        res = transaction(sum-1);
        for(int x:res.ff) cnt[x]++;
        dnc(s+1, e, sum-1);
        return;
    }

    ll avg = sum/sz;
    res = transaction(avg);
    for(int x:res.ff) cnt[x]++;
    int idx = res.ff[0];
    dnc(idx, e, avg);

    while(v.size() && v.back() >= idx) {
        sum -= arr[v.back()]; v.pop_back();
    }

    res = make_pair(v, 0);
    dnc(s, idx-1, sum);
}

void buy_souvenirs(int N, ll P0) {
    res = transaction(P0-1);
    for(int x:res.ff) cnt[x]++;
    dnc(1, N-1, P0-1);

    for(int i=1; i<N; i++) {
        while(cnt[i] < i) {
            transaction(arr[i]);
            cnt[i]++;
        }
    }
}

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