Submission #1250550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250550		nikd	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void buy_souvenirs(int N, long long P0) {
  //std::pair<std::vector<int>, long long> res = transaction(3);
  vector<ll> P(N, -1);
  P[0] = P0;
  vector<int> buyed(N, 0);
  auto rec = [&](auto&& rec, ll pos)->int{
    auto [vec, r] = transaction(pos);
    ll rim = pos-r;
    int idx = vec[0];
    int cnt = vec.size();
    vector<bool> removed(cnt, 0);
    for(int i = 0; i<vec.size(); i++){
      buyed[vec[i]]++;
      if(P[vec[i]] != -1){
        rim -= P[vec[i]];
        cnt--;
        removed[i] = 1;
      }
    }
    if(cnt == 1){
      P[idx] = rim;
      if(idx != N-1 && P[idx+1] == -1) rec(rec, rim-1);
      return idx;
    }
    for(int i = vec.size()-1; i>0; i--){
      if(removed[i]){
        assert(P[vec[i]] != -1);
        continue;
      }
      int i2 = rec(rec, (rim+cnt-1)/cnt-1);
      i = lower_bound(vec.begin(), vec.end(), i2)-vec.begin();
      for(int j = i; j<vec.size(); j++){
        if(removed[j]) continue;
        assert(P[vec[j]] != -1); 
        removed[j] = 1;
        cnt--;
        rim -= P[vec[j]];
      }
    }
    P[idx] = rim;
    if(idx != N-1 && P[idx+1] == -1) rec(rec, rim-1);
    return idx;
  };
  rec(rec, P0-1);
  for(int i =1; i<N; i++){
    while(buyed[i] < i){
      transaction(P[i]);
      buyed[i]++;
    }
  }
  return;
}

• 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