Submission #1258124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258124		alexdd	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	0 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int fr[105],val[105];
void buy_souvenirs(int n, long long p0)
{
    for(int pas=n-1;pas>1;pas--)
    {
        int cur = p0, cate = pas;
        val[pas] = -1;
        while(cate > 1)
        {
            pair<vector<int>, ll> aux = transaction(cur/cate);
            ll sum = cur/cate - aux.second;
            cate = 0;
            for(int x:aux.first)
            {
                fr[x]++;
                if(x <= pas)
                {
                    cate++;
                }
                else
                {
                    sum -= val[x];
                }
            }
            assert(sum <= cur);
            cur = sum;
        }
        assert(cate==1);
        val[pas] = cur;
    }
    pair<vector<int>, ll> aux = transaction(p0 - 1);
    val[1] = (p0 - 1) - aux.second;
    for(int x:aux.first)
    {
        fr[x]++;
        if(x > 1)
            val[1] -= val[x];
    }
    for(int i=1;i<n;i++)
    {
        assert(fr[i] <= i);
        while(fr[i] < i)
        {
            transaction(val[i]);
            fr[i]++;
        }
    }
}
/*

3
4 3 2

*/

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