Submission #1251996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251996		Gabp	Souvenirs (IOI25_souvenirs)	C++20	Compilation error	0 ms	0 KiB

souvenirs

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

void buy_souvenirs(int n, long long int P0) {
  vector<int> cnt(n, 0);
  vector<long long int> vals(n, -1);
  
  auto find_min = [&](long long int total, int sz) -> long long int {
    long long int lo = sz, hi = total;
    long long int res;
    while (lo <= hi) {
      long long int mid = lo + (hi - lo) / 2;
      long long int last = mid - sz + 1;
      long long int sum = (mid + last) * sz / 2;
      long long int left = total - sum;
      if (left >= last - 1) {
        lo = mid + 1;
      } else {
        res = mid;
        hi = mid - 1;
      }
    }
    return res;
  };
  
  long long int prev = P0;
  vector<pair<vector<int>,long long int>> hist;
  vector<long long int> queries;
  for (int i = 1; i < n; i++) {
    auto data = transaction(prev - 1);
    hist.push_back(data);
    queries.push_back(prev - 1);
    auto [list, m] = data;
    assert(list[0] == i);
    for (auto j: list) cnt[j]++;
    
    if (list.size() == 1) {
      vals[i] = prev - 1 - m;
      prev = vals[i];
      continue;
    }
    
    if (list.size() == n - i) {
      long long int total = prev - 1 - m;
      long long int lo = n - i, hi = total;
      while (lo <= hi) {
        long long int mid = lo + (hi - lo) / 2;
        long long int sum = (2 * mid + 1 - i + n) * (n - i) / 2;
        if (total - sum <= 0) {
          prev = mid;
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      }
      continue;
    }
    
    int sz = 1;
    while (sz < list.size() && list[sz] == i + sz) sz++;
    
    prev = find_min(prev - 1, sz);
  }
  
  for (int i = n - 1; i > 0; i--) {
    if (val[i] != -1) continue;
    val[i] = queries[i - 1];
    auto [list, m] = hist[i - 1];
    
    val[i] -= m;
    for (int j = 1; j < list.size(); j++) val[i] -= val[list[j]];
  }
  
  for (int i = 1; i < n; i++) {
    for (int j = cnt[i]; j < i; j++) {
      transaction(val[i]);
    }
  }
}

Compilation message (stderr)

souvenirs.cpp: In function 'void buy_souvenirs(int, long long int)':
souvenirs.cpp:30:17: error: 'transaction' was not declared in this scope
   30 |     auto data = transaction(prev - 1);
      |                 ^~~~~~~~~~~
souvenirs.cpp:66:9: error: 'val' was not declared in this scope; did you mean 'vals'?
   66 |     if (val[i] != -1) continue;
      |         ^~~
      |         vals
souvenirs.cpp:67:5: error: 'val' was not declared in this scope; did you mean 'vals'?
   67 |     val[i] = queries[i - 1];
      |     ^~~
      |     vals
souvenirs.cpp:76:19: error: 'val' was not declared in this scope; did you mean 'vals'?
   76 |       transaction(val[i]);
      |                   ^~~
      |                   vals
souvenirs.cpp:76:7: error: 'transaction' was not declared in this scope
   76 |       transaction(val[i]);
      |       ^~~~~~~~~~~