제출 #1264343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264343		garyye	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAX_N = 100;

int bought[MAX_N];
ll price[MAX_N];
int N;

ll div_ceil(ll a, ll b) {
  return (a + b - 1) / b;
}

pair<vector<int>, ll> my_transaction(ll T) {
  auto [I, R] = transaction(T);
  for(int i: I) {
    bought[i] ++;
  }
  return {I, R};
}

// Transaction cost T
// Indices return I
// Remainder R
void solve(ll T, vector<int> I, ll R) {
  if(I.size() == 1) {
    price[I[0]] = T - R;
    if(I[0] + 1 < N) {
      T = price[I[0]] - 1;
      auto [I, R] = my_transaction(T);
      solve(T, I, R);
    }
    return;
  }

  ll rhs = T - R;
  for(int i = I.size() - 1; i >= 1; i--) {
    // Price already known
    if(price[I[i]] > 0) {
      rhs -= price[I[i]];
    } else {
      ll T1 = div_ceil(rhs, (i + 1)) - 1;
      auto [I1, R1] = my_transaction(T1);
      solve(T1, I1, R1);

      // Now it should be known because we solved for that suffix
      assert(price[I[i]] > 0);
      rhs -= price[I[i]];
    }
  }
  price[I[0]] = rhs;

  // Now recursively solve for the remainder of the suffix
  for(int k = I[0] + 1; k < N; k++) {
    if(price[k] == 0) {
      ll T1 = price[k - 1] - 1;
      auto [I1, R1] = my_transaction(T1);
      solve(T1, I1, R1);
      break;
    }
  }
}

void buy_souvenirs(int _N, ll P0) {
  N = _N;
  price[0] = P0;

  auto [I, R] = my_transaction(P0 - 1);
  solve(P0 - 1, I, R);

  for(int i = 0; i < N; i++) {
    assert(price[i] > 0);
    int rem = i - bought[i];
    for(int j = 0; j < rem; j++) {
      auto [I, R] = my_transaction(price[i]);
      assert(R == 0);
      assert(I.size() == 1);
      assert(I[0] == 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