Submission #1252527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252527		WongYiKai	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

pair<vector<int>,ll> convert(pair<vector<int>,ll> query, int N){
    vector<int> temp(N,0);
    for (int i=0;i<query.first.size();i++){
        temp[query.first[i]] = 1;
    }
    return {temp,query.second};
}

void buy_souvenirs(int N, long long p0){
    ll bought2[N+5];
    memset(bought2,0,sizeof(bought2));
    ll price[N+5];
    memset(price,-1,sizeof(price));
    price[0] = p0;
    ll mn = p0-1;
    pair<vector<int>,long long> query = transaction(mn);
    query = convert(query,N);
    for (int i=0;i<query.first.size();i++){
        bought2[i] += query.first[i];
    }
    priority_queue<pair<vector<int>,pair<ll,ll>>,vector<pair<vector<int>,pair<ll,ll>>>,greater<pair<vector<int>,pair<ll,ll>>>> pq;
    pq.push({query.first,{query.second,mn}});
    int back = N-1;
    while (!pq.empty()){
        ll next = -1;
        pair<vector<int>,pair<ll,ll>> query = pq.top();
        //pq.pop();
        vector<int> items;
        int ind = -1;
        ll total = 0;
        for (int i=0;i<N;i++){
            if (query.first[i]==1 && price[i]==-1) {
                items.push_back(i);
                ind = max(ind,i);
            }
            else if (query.first[i]==1 && price[i]!=-1) total += price[i];
        }
        if (items.size()==0){
            pq.pop();
        }
        else if (items.size()==1){
            pq.pop();
            price[ind] = query.second.second - query.second.first - total;
            next = price[ind] - 1;
            while (back>=0 && price[back]!=-1){
                back--;
            }
        }
        else{
            next = (query.second.second - query.second.first - total)/items.size();
        }
        if (ind<=back && items.size()>0){
            pair<vector<int>,ll> q = transaction(next);
            q = convert(q,N);
            for (int i=0;i<q.first.size();i++){
                bought2[i] += q.first[i];
            }
            if (next==-1) break;
            pq.push({q.first,{q.second,next}});
        } 
        items.clear();
    }
    //for (int i=0;i<N;i++) cout << price[i] << ' ';
    //cout << "\n";
    // for (int i=0;i<N;i++){
    //     cout << bought[i] << ' ';
    //     // if (bought[i]>i){
    //     //     cout << "too many " << bought[i] << ' ' << i << "\n"; 
    //     // }
    // }
    // cout << "\n";
    for (int i=0;i<N;i++){
        for (int j=0;j<i-bought2[i];j++){
            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