Submission #1251105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251105		abcdxyz123	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 vi vector<int>
#define fi first
#define se second
vector<ll>p;
vector<int>cnt;
int Refresh(ll &sum,vector<int>&cur)
{
    int old=cur.size();
    set<int>s;
    for(int v:cur)
    {
        s.insert(v);
    }
    for(int v:cur)
    {
        if(p[v]!=-1)
        {
            sum-=p[v];
            s.erase(v);
        }
    }
    cur.clear();
    for(int v:s)cur.push_back(v);
    return (old>cur.size());
}
void dfs(int u,ll sum,vector<int>cur)
{
    if(cur.size()==1)
    {
        p[u]=sum;
        return ;
    }
    if(p[u]!=-1)assert(0);
    Refresh(sum,cur);
    while(true)
    {
        if(cur.size()==1)
        {
            p[u]=sum;
            break;
        }
        ll nxt_sum=sum/cur.size();
        for(int i=cur.back(); i>=u; i--)
        {
            if(p[i]!=-1)
            {
                nxt_sum=p[i]-1;
                break;
            }
        }
        pair<vi,ll>nxt=transaction(nxt_sum);
        for(int v:nxt.fi)cnt[v]++;
        nxt_sum-=nxt.se;
        dfs(nxt.fi[0],nxt_sum,nxt.fi);
        Refresh(sum,cur);
    }
}
void buy_souvenirs(int n,ll p0)
{
    p=vector<ll>(n,-1);
    p[0]=p0;
    cnt=vector<int>(n,0);
    for(int i=1; i<n; i++)
    {
        if(p[i]==-1)
        {
            ll nxt_sum=p[i-1]-1;
            pair<vi,ll>nxt=transaction(nxt_sum);
            for(int v:nxt.fi)cnt[v]++;
            nxt_sum-=nxt.se;
            Refresh(nxt_sum,nxt.fi);
            dfs(nxt.fi[0],nxt_sum,nxt.fi);
        }
    }
    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