Submission #1249379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249379		model_code	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

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

using namespace std;

const int N=105;

struct payment{
    vector<int> items;
    long long price;
};

payment leading[N];
long long price[N];
int cnt_bought[N];
int know_leading;

pair<vector<int> , long long> add_leading(long long curp)
{
    auto ret=transaction(curp);
    sort(ret.first.begin(), ret.first.end());
    if(leading[ret.first[0]].price == 0) know_leading++;
    leading[ret.first[0]] = {ret.first, curp - ret.second};
    for(int i:ret.first) cnt_bought[i]++;
    return ret;
}

void calc_price(int i)
{
    long long me = leading[i].price;
    for(int j:leading[i].items) if(j!=i) me-=price[j];
    price[i] = me;
}

void buy_souvenirs(int n, long long P0)
{
    long long curp = P0 - 1;
    for(int i=0;i<n;i++) leading[i] = {vector<int>(), 0};
    while(true)
    {
        auto ret=add_leading(curp);
        curp -= ret.second;
        curp = curp/ret.first.size();
        if(ret.first.size() == 1) curp--; // In case of exactly one item bought
        if(ret.first[0] == n-1) break; 
    }
    while(know_leading < n-1) {
        int unknown = n-1;
        while(leading[unknown].price) {
            if(!price[unknown]) calc_price(unknown);
            unknown--;
        }   
        int known = unknown;
        while(leading[known].price == 0) known--;
        long long totp = leading[known].price;
        int totn = leading[known].items.size();
        for(int j:leading[known].items) {
            if(j > unknown) {
                if(!price[j]) calc_price(j);
                totn--;
                totp -= price[j];
            }
        }
        if(totn == 1) totp--;
        else totp/=totn;
        auto ret = add_leading(totp);
        int cnt_unknown = ret.first.size();
        long long tot = totp - ret.second;
        for(int i:ret.first)
        {
            if(price[i]) {
                tot-=price[i];
                cnt_unknown--;
            }
        }
        if(cnt_unknown == 1) {
            price[ret.first[0]] = tot;
        }
    }
    for(int i=n-1;i>=0;i--)
    {
        long long me = leading[i].price;
        for(int j:leading[i].items) if(j!=i) me-=price[j];
        price[i] = me;
        while(cnt_bought[i] < i) {
            transaction(price[i]);
            cnt_bought[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