Submission #1251030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251030		flashmt	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;

int n;
vector<int> bought;
vector<long long> p;

pair<vector<int>, long long> buy(long long coins)
{
  auto [ids, rem] = transaction(coins);
  for (int i : ids)
    bought[i]++;
  return {ids, coins - rem};
}

void go(long long maxP)
{
  auto [ids, cost] = buy(maxP);
  int curId = ids[0], sz = size(ids);

  for (int i = sz - 1; i; i--)
  {
    int id = ids[i];
    if (p[id] == 0)
      go(cost / (i + 1));
    cost -= p[id];
  }

  p[curId] = cost;

  for (int i = curId + 1; i < n; i++)
    if (p[i] == 0)
    {
      go(p[i - 1] - 1);
      return;
    }
}

void buy_souvenirs(int N, long long p0) {
  n = N;
  bought.assign(n, 0);
  p.assign(n, 0);
  go(p0 - 1);
  for (int i = 1; i < n; i++)
  {
    assert(bought[i] <= i && p[i] > 0);
    while (bought[i] < i)
      buy(p[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