Submission #1260263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260263		truongdz_top12	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
int N,Q[1111];
long long P[1111];
void ask(int N,long long M)
{
    pair<vector<int>,long long>buy=transaction(M);
    for(auto&i:buy.first)
        ++Q[i];
    auto previous=buy;
    while(true)
    {
        buy=previous;
        while(!buy.first.empty()&&P[buy.first.back()])
        {
            buy.second+=P[buy.first.back()];
            buy.first.pop_back();
        }
        if(buy.first.size()==1&&(buy.first[0]==N-1||P[buy.first[0]+1]))
        {
            P[buy.first[0]]+=M-buy.second;
            break;
        }
        if(buy.first.size()==1)
            ask(N,M-buy.second-1);
        else
            ask(N,(M-buy.second)/buy.first.size());
    }
}
void buy_souvenirs(int N,long long P0)
{
    P[0]=P0;
    ask(N,P0-1);
    for(int i=0;i<N;++i)
    {
        while(Q[i]<i)
        {
            transaction(P[i]);
            ++Q[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