Submission #1272102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272102		thewizardman	Souvenirs (IOI25_souvenirs)	C++20	3 / 100	13 ms	392 KiB

souvenirs

#include "souvenirs.h"
#include <map>
using namespace std;
using ll = long long;

int n;
ll p[100], cnt[100];
bool flag[100];

map<ll, pair<vector<int>, ll>> ma;

ll calc(pair<vector<int>, ll>& x) {
  ll l = 0, r = x.second, mid = 0, ret = -1;
  while (l < r) {
    mid = (l + r) >> 1;
    ll cur = 0;
    for (auto e: x.first) cur += mid - e + x.first[0];
    if (cur < x.second) ret = mid, l = mid + 1;
    else r = mid - 1;
  }
  return ret;
}

pair<vector<int>, ll> buy(ll m) {
  pair<vector<int>, ll> ret;
  vector<int> a;
  if (ma.count(m)) ret = ma[m];
  else {
    ma[m] = ret = transaction(m);
    for (auto e: ret.first) cnt[e]++;
  }
  ret.second = m - ret.second;
  for (auto e: ret.first) {
    if (p[e]) ret.second -= p[e];
    else a.push_back(e);
  }
  return {a, ret.second};
}

void solve(int m) {
  if (ma.count(m)) return;
  pair<vector<int>, ll> res = buy(m);
  flag[res.first[0]] = 1;
  while (res.first.size() > 1) {
    solve(calc(res));
    res = buy(m);
  }
  if (res.first.size() == 1) {
    p[res.first[0]] = res.second;
    if (res.first[0] != n-1 && !flag[res.first[0] + 1]) solve(res.second - 1);
  }
}

void buy_souvenirs(int N, long long P0) {
  n = N;
  p[0] = P0;
  for (int i = 1; i < n; i++) if (!p[i]) solve(p[i-1] - 1);
  for (int i = 0; i < n; i++) for (int j = 0; j < i-cnt[i]; j++) transaction(p[i]);
}

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