Submission #1319416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319416		Trisanu_Das	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	18 ms	408 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second

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

pair<vector<int>, ll> qry(ll val){
    auto res = transaction(val);
    for(auto &x : res.ff) A[x]++;
    return res;
}

int dfs(ll val, int M){
    auto [V, R] = qry(val);
    assert(V[0] < M);
    ll T = val - R;
    int cur = V[0];
    while(1){
        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, ll P0){
    ::N = N;
    dfs(P0 - 1, N);
    for(int i = 1; i < N; i++)
        for(int j = A[i]; j < i; j++)
            qry(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