Submission #1255659

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

souvenirs

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

#define ll long long
#define pb push_back

struct Query{
    vector<int> ids;
    ll sum;

    Query(ll X,pair<vector<int>,ll> res){
        ids=res.first;
        sort(ids.begin(),ids.end());
        sum=X-res.second;
    }
};

void buy_souvenirs(int n, ll P0) {
    vector<int> cnt(n,0);
    vector<ll> P(n);
    P[0]=P0;

    vector<Query> Qs;
    while(true){
        while(true){
            bool upd=false;
            for(Query q:Qs){
                int unk=0,taj;
                ll sum=0;
                for(int i:q.ids){
                    if(P[i]==0)unk++,taj=i;
                    else sum+=P[i];
                }
                if(unk==1){
                    P[taj]=q.sum-sum;
                    upd=true;
                }
            }
            if(!upd)break;
        }

        //for(int i=0;i<n;i++)printf("%lld ",P[i]);
        //printf("\n");

        int ptr=n;
        while(ptr>0&&P[ptr-1]!=0)ptr--;
        if(ptr==0)break;

        ll X=P0-1;
        for(Query q:Qs){
            int lo=0;
            ll sum=0;
            for(int i:q.ids){
                if(i<ptr)lo++;
                else sum+=P[i];
            }
            if(lo){
                if(lo==1){
                    X=min(X,q.sum-sum-1);
                }else{
                    X=min(X,(q.sum-sum)/lo);
                }
            }
        }
        auto res=transaction(X);
        Qs.pb(Query(X,res));
        for(int i:Qs.back().ids){
            cnt[i]++;
        }
    }
    for(int i=1;i<n;i++){
        while(cnt[i]<i){
            transaction(P[i]);
            cnt[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