Submission #1251469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251469		windowwife	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	14 ms	6696 KiB

souvenirs

#ifndef rtgsp
#include "souvenirs.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 2e5 + 2;
int n, q[maxn];
ll p[maxn], tot, cnt;
pair<vector<int>, ll> v, t[maxn];

#ifdef rtgsp
ll pp[maxn];
pair<vector<int>, ll> transaction (ll M)
{
    vector<int> s;
    s.clear();
    for (int i = 0; i < n; i++)
    {
        if (M >= pp[i])
        {
            M -= pp[i];
            s.push_back(i);
        }
    }
    return make_pair(s, M);
}
#endif // rtgsp

void buy_souvenirs(int N, ll P0)
{
    n = N;
    tot = P0; cnt = 1;
    for (int i = 1; i < n; i++) t[i] = {{}, 0};
    while (true)
    {
        assert(tot > 0);
        if (cnt == 1)
        {
            v = transaction(tot - 1);
            tot = tot - 1 - v.second;
            cnt = v.first.size();
            t[v.first[0]] = {v.first, tot};
            for (int i : v.first) q[i]++;
        }
        else
        {
            v = transaction(tot/cnt);
            tot = tot/cnt - v.second;
            cnt = v.first.size();
            t[v.first[0]] = {v.first, tot};
            for (int i : v.first) q[i]++;
        }
        if (v.first[0] == n - 1) break;
    }
    for (int i = n - 1; i > 0; i--)
    {
        if (t[i].second == 0)
        {
            for (int j = i - 1; j > 0; j--)
            {
                if (t[j].second == 0) continue;
                tot = t[j].second; cnt = t[j].first.size();
                for (int k : t[j].first)
                {
                    if (k > i)
                    {
                        tot -= p[k];
                        cnt--;
                    }
                }
                break;
            }
            while (true)
            {
                if (cnt == 1)
                {
                    v = transaction(tot - 1);
                    tot = tot - 1 - v.second;
                    cnt = v.first.size();
                    t[v.first[0]] = {v.first, tot};
                    for (int j : v.first) q[j]++;
                }
                else
                {
                    v = transaction(tot/cnt);
                    tot = tot/cnt - v.second;
                    cnt = v.first.size();
                    t[v.first[0]] = {v.first, tot};
                    for (int j : v.first) q[j]++;
                }
                for (int j : v.first)
                {
                    if (j > i)
                    {
                        tot -= p[j];
                        cnt--;
                    }
                }
                if (v.first[0] == i) break;
            }
        }
        for (int j : t[i].first)
            p[i] -= p[j];
        p[i] += t[i].second;
    }
    for (int i = 1; i < n; i++)
    {
        while (q[i] < i)
        {
            v = transaction(p[i]);
            assert(v.first.size() == 1);
            for (int j : v.first) q[j]++;
        }
    }
}

#ifdef rtgsp
int main()
{
    freopen(task".in", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    vector<ll> P;
    P.clear();
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        ll x;
        cin >> x;
        pp[i] = x;
        P.push_back(x);
    }
    buy_souvenirs(N, P[0]);
}
#endif // rtgsp

• 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