제출 #1367303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367303		edga1	선물 (IOI25_souvenirs)	C++20	100 / 100	44 ms	460 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), ban(5000,0);
    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;
        for(int j=0; j<pt.size(); j++){
            int e=0;
            if(ban[j]) continue;
            auto ar=pt[j].se.fi;
            for(int i=0; i<ar.size(); i++){
                if(ma[ar[i]]!=mi[ar[i]]) e=1;
            }
            if(!e) ban[j]=1;
        }
        ll t=0;
        while(e){
            t++;
            if(t==10) break;
            e=0;
            for(int k=0; k<pt.size(); k++){
                if(ban[k]) continue;
                ll c=pt[k].fi, ret=pt[k].se.se;
                vector<int> s=pt[k].se.fi;
                ll e2=0;
                for(ll i=0; i<s.size(); i++){
                    if(ma[s[i]]==mi[s[i]]) continue;
                    e2=1;

                    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);
                        }
                    }
                }
                if(!e2){
                    ban[k]=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;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 4 / 4
• 서브태스크 2: 3 / 3
• 서브태스크 3: 14 / 14
• 서브태스크 4: 18 / 18
• 서브태스크 5: 28 / 28
• 서브태스크 6: 33 / 33