Submission #1249443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249443		jtnydv25	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	11 ms	424 KiB

souvenirs

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

void buy_souvenirs(int n, long long P0){
  vector<long long> P(n, P0);
  vector<int> cnt(n);

  function<pair<vector<int>, long long>(long long, int)> query = [&](long long m, int k){
      pair<vector<int>, long long> res = transaction(m);
      vector<int> &c = res.first;
      long long p = res.second;
      long long used = m - p;
      for(int i: c) cnt[i]++;
      while(!c.empty() && c.back() >= k){
          used -= P[c.back()];
          c.pop_back();
      }
      assert(!c.empty());
      return make_pair(c, used);
  };

  function<int(long long, int)> get = [&](long long X, int k){
      pair<vector<int>, long long> Q = query(X, k);
      vector<int> S = Q.first;
      long long sm = Q.second;
      int i = S[0];
      while((int)S.size() > 1){
          k = get((sm - 1) / (int)S.size(), k);
          while(!S.empty() && S.back() >= k){
              sm -= P[S.back()];
              S.pop_back();
          }
          assert(!S.empty());
      }
      P[i] = sm;
      if(k > i + 1) get(P[i] - 1, k);
      return i;
  };

  get(P[0] - 1, n);

  for(int i = 0; i < n; i++){
      while(cnt[i] < i){
          transaction(P[i]);
          cnt[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