Submission #1250998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250998		flashmt	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	12 ms	412 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], nextId = curId;
  for (int i : ids)
    if (i == nextId)
      nextId++;

  int len = nextId - curId;
  if (size(ids) == 1)
  {
    p[curId] = cost;
    if (curId < n - 1)
      go(cost - 1);
  }
  else
  {
    // xxx..x.x
    go(cost / (len + 1));
    for (int i : ids)
      if (i > nextId)
        cost -= p[i];

    // xxx.....
    for (int i = len; i >= 2; i--)
    {
      int id = curId + i - 1;
      if (p[id] == 0)
        go(cost / len);
      cost -= p[id];
    }

    p[curId] = cost;
  }
}

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: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33