Submission #1271746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271746		thewizardman	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	11 ms	408 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>

using namespace std;
using ll = long long;

void a(int l, int r);
void b(int l, int r, vector<int>& v, ll sum);

ll p[100], cnt[100];

void buy_souvenirs(int N, long long P0) {
  p[0] = P0;
  a(1, N);
  for (int i = 0; i < N; i++) {
    // cout << p[i] << ' ';
    for (int j = 0; j < i-cnt[i]; j++) transaction(p[i]);
  }
}

void a(int l, int r) {
  if (l >= r) return;
  if (l == r-1) {
    ll u = p[l-1]-1;
    pair<vector<int>, ll> v = transaction(u);
    for (auto e: v.first) cnt[e]++;
    for (auto e: v.first) if (e >= r) u -= p[e];
    for (auto e: v.first) if (e >= r) v.first.erase(lower_bound(v.first.begin(), v.first.end(), e));
    p[l] = u - v.second;
    return;
  }
  ll u = p[l-1]-1;
  pair<vector<int>, ll> v = transaction(u);
  for (auto e: v.first) cnt[e]++;
  for (auto e: v.first) if (e >= r) u -= p[e];
  for (auto e: v.first) if (e >= r) v.first.erase(lower_bound(v.first.begin(), v.first.end(), e));
  if (v.first.size() == 1) p[v.first[0]] = u-v.second;
  b(l, v.first.back()+1, v.first, u-v.second);
  a(v.first.back()+1, r);
}

void b(int l, int r, vector<int>& v, ll sum) {
  if (l >= r || v.empty()) return;
  if (l == r-1) {
    for (auto e: v) if (e >= r) sum -= p[e];
    for (auto e: v) if (e >= r) v.erase(lower_bound(v.begin(), v.end(), e));
    p[v[0]] = sum;
    return;
  }
  ll L = 0, R = sum, mid, u;
  while (L < R) {
    mid = (L + R) >> 1;
    ll check = 0;
    for (auto e: v) check += mid + (l-e);
    if (check >= sum) R = mid - 1;
    else L = mid + 1, u = mid;
  }
  pair<vector<int>, ll> w = transaction(u);
  for (auto e: w.first) cnt[e]++;
  for (auto e: w.first) if (e >= r) u -= p[e];
  for (auto e: w.first) if (e >= r) w.first.erase(lower_bound(w.first.begin(), w.first.end(), e));
  if (w.first.size() == 1) p[w.first[0]] = u-w.second;
  b(w.first[0], w.first.back()+1, w.first, u-w.second);
  a(w.first.back()+1, r);
  vector<int> k;
  for (auto e: v) if (e >= l) sum -= p[e];
  for (auto e: v) if (e < w.first[0]) k.push_back(e);
  b(l, w.first[0], k, sum);
}

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