Submission #1273280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273280		sakibulislam	Souvenirs (IOI25_souvenirs)	C++17	100 / 100	13 ms	400 KiB

souvenirs

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

typedef long long ll;



void buy_souvenirs(int N, long long P0) {
    vector<ll> price(N, -1);
    vector<int> cnt(N, 0);
    vector<set<int>> st(N);
    vector<ll> sum(N, 0);

    price[0]=P0;

    bool br;
    while (true){
        br = true;
        for (int i=0; i<N; i++) if (price[i]==-1)br=false;
        if (br) break;

        bool found = false;
        for (int i=N-1; i>=0; i--){
            if (price[i]==-1 && !found) found=true;

            if (price[i]!=-1 && found){
                auto [lis, ret] = transaction(price[i]-1);

                set<int> ss;
                for (int x:lis) ss.insert(x), cnt[x]++;

                ll rest = price[i]-1-ret;

                for (int j=i+1; j<N; j++) if (price[j]!=-1 && ss.count(j)){
                     ss.erase(j);
                     rest-= price[j];

                }

                st[i+1] = ss;
                sum[i+1] = rest;
                break;                
            }

            if (st[i].size()==1){
                price[i] = sum[i];
                st[i].clear();

                for (int j=0; j<i; j++) if (st[j].count(i)){
                    st[j].erase(i);
                    sum[j]-=price[i];
                }
                break;
            }

            if (st[i].size()){
                ll x = sum[i]/ (ll) st[i].size();
                auto [lis, ret] = transaction(x);

                set<int> ss;
                for (int y:lis) ss.insert(y), cnt[y]++;

                ll rest = x-ret;

                for (int j=lis[0]; j<N; j++) if (price[j]!=-1 && ss.count(j)){
                     ss.erase(j);
                     rest-= price[j];

                }

                st[lis[0]] = ss;
                sum[lis[0]] = rest;
                break;     
            }
        }
    }

    for (int i=0; i<N; i++){
        while (cnt[i]<i){
            cnt[i]++;
            transaction(price[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