Submission #1302459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302459		regulardude6	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	13 ms	332 KiB

souvenirs

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

static int n;
static long long p0;
static vector<long long> price;
static vector<long long> bought;

static pair<vector<int>, long long> ask(long long M){
    auto res = transaction(M);
    for(int x : res.first) bought[x]++;
    return res;
}

static void deduce(int idx, long long limit){
    if(idx <= 0 || idx >= n) return;
    if(price[idx] != -1) return;

    auto res = ask(limit);
    if(res.first.empty()) return;

    long long spent = limit - res.second;
    int id = res.first[0];
    price[id] = spent;
}

void buy_souvenirs(int N, long long P0){
    n = N;
    p0 = P0;

    price.assign(n, -1);
    bought.assign(n, 0);

    price[0] = P0;

    for(int i = 1; i < n; i++){
        long long lim = price[i-1] - 1;
        if(lim <= 0) break;
        deduce(i, lim);
    }

    for(int i = 1; i < n; i++){
        if(price[i] <= 0) continue;
        while(bought[i] < i){
            ask(price[i]);
        }
    }
}

• 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