Submission #1364062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364062		edga1	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	1091 ms	344 KiB

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;

void buy_souvenirs(int n, long long P0) {
    vector<ll> b(n,0), mi(n), ma(n);
    ma[0]=mi[0]=P0;
    for(int i=n-1; i>0; i--){
        mi[i]=n-i;
        ma[i]=P0-i;
    }
    int pos=n-1;
    vector<pair<ll,pair<vector<int>,ll>>> pt;
    while(pos!=0){
        if(ma[pos]==mi[pos]){
            pos--;
            continue;
        }
        pair<vector<int>,ll> res=transaction(ma[pos]);
        pt.pb({ma[pos],res});
        for(auto au : res.fi) b[au]++;
        int e=1;
        while(e){
            e=0;
            for(auto au : pt){
                ll c=au.fi, ret=au.se.se;
                vector<int> s=au.se.fi;
                for(ll i=0; i<s.size(); i++){
                    if(ma[s[i]]==mi[s[i]]) continue;

                    ll cmi=ret;
                    for(ll j=i+1; j<s.size(); j++){
                        cmi+=mi[s[j]];
                    }
                    ll l=mi[s[i]],r=ma[s[i]];
                    while(l<=r){
                        ll mid=(l+r)/2;
                        ll cmi2=0;
                        for(int j=0; j<i; j++){
                            cmi2+=max(mi[s[j]],mid+s[i]-s[j]);
                        }
                        if(cmi2+cmi+mid<=c) l=mid+1;
                        if(cmi2+cmi+mid>c) r=mid-1;
                    }
                    if(r!=ma[s[i]]){
                        ma[s[i]]=r;
                        e=1;
                        for(int j=s[i]+1; j<n; j++){
                            ma[j]=min(ma[j],ma[j-1]-1);
                        }
                    }

                    ll cma=ret;
                    for(ll j=0; j<i; j++){
                        cma+=ma[s[j]];
                    }
                    l=mi[s[i]],r=ma[s[i]];
                    while(l<=r){
                        ll mid=(l+r)/2;
                        ll cma2=0;
                        for(int j=i+1; j<s.size(); j++){
                            cma2+=min(ma[s[j]],mid+s[i]-s[j]);
                        }
                        if(cma2+cma+mid<=c) l=mid+1;
                        if(cma2+cma+mid>c) r=mid-1;
                    }
                    if(r!=mi[s[i]]){
                        mi[s[i]]=r;
                        e=1;
                        for(int j=s[i]-1; j>0; j--){
                            mi[j]=max(mi[j],mi[j+1]+1);
                        }
                    }
                }
            }
        }
    }
    for(int i=1; i<n; i++){
        for(int j=0; j<i-b[i]; j++){
            pair<vector<int>,ll> res=transaction(ma[i]);
        }
    }
    return;
}

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