Submission #1252506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252506		anfi	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	0 ms	412 KiB

souvenirs

#include"souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const long long inf = 1e9;
long long n,last,p[105],cn[105];
long long hitung(int s, int k){
    s += k*(k-1)/2+k-1;
    return s/k;
}

void fin(long long initial_money) {
    vector<long long> money_stack;
    vector<vector<int>> v_stack;
    vector<long long> sum_stack;
    vector<int> stage_stack;

    money_stack.push_back(initial_money);
    v_stack.emplace_back(); 
    sum_stack.push_back(0);
    stage_stack.push_back(0); 

    while (!money_stack.empty()) {
        int d = money_stack.size() - 1;

        if (stage_stack[d] == 0) {
            auto [v, remain] = transaction(money_stack[d]);
            v_stack[d] = v;
            sum_stack[d] = money_stack[d] - remain;

            for (int i : v)
                cn[i]++;

            if (v[0] < last) {
                while (!v.empty() && v.back() >= last) {
                    sum_stack[d] -= p[v.back()];
                    v.pop_back();
                }

                v_stack[d] = v;

                if (v[0] + 1 != last) {
                    long long new_money = hitung(sum_stack[d], v.size()) - 1;
                    money_stack.push_back(new_money);
                    v_stack.emplace_back(); 
                    sum_stack.push_back(0);
                    stage_stack.push_back(0);
                    continue;
                }
            }

            stage_stack[d] = 1; 
        }

        if (stage_stack[d] == 1) {
            int idx = v_stack[d][0];
            p[idx] = sum_stack[d];
            last = idx;

            money_stack.pop_back();
            v_stack.pop_back();
            sum_stack.pop_back();
            stage_stack.pop_back();
        }
    }
}


void buy_souvenirs(int N, long long p0){ 
    memset(cn, 0, sizeof(cn));
    memset(p, 0, sizeof(p));
    p[0] = p0, n = N;
    fin(p0-1);
    for(int i = 1; i < N; i++){
        while(cn[i] < i){
            transaction(p[i]);
            cn[i]++;
        }
    }
}

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