Submission #1259045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259045		alexdd	Souvenirs (IOI25_souvenirs)	C++20	22 / 100	12 ms	428 KiB

souvenirs

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

3
4 3 2

3
4 2 1

*/

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