Submission #1249533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249533		qwerasdfzxcl	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int N, a[101];
ll P[101];

pair<vector<int>, ll> query(ll val){
    auto ret = transaction(val);
    for (auto &x:ret.first) a[x]++;
    return ret;
}

int dfs(ll val, int M){
    auto [V, R] = query(val);
    assert(V[0] < M);

    ll T = val - R;
    int cur = V[0];

    while(true){
        while(V.back() >= M){
            T -= P[V.back()];
            V.pop_back();
        }

        if (cur+1 == M) break;
        M = dfs((T-1) / (int)V.size(), M);
    }

    P[cur] = T;
    return cur;
}

void buy_souvenirs(int N, long long P0){
    ::N = N;
    dfs(P0-1, N);

    for (int i=1;i<N;i++){
        for (int j=a[i];j<i;j++) query(P[i]);
    }
}

• 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