Submission #1251207

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

souvenirs

//IOI 2025 Day 1 Problem A 

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()
#define vi vector<int>
#define f first
#define s second 
#include "souvenirs.h"

/*
namespace {
const int CALLS_CNT_LIMIT = 10'000;

int calls_cnt;
int N;
std::vector<long long> P;
std::vector<int> Q;

void quit(const char* message) {
  printf("%s\n", message);
  exit(0);
}
} // namespace

std::pair<std::vector<int>, long long> transaction(long long M) {
  calls_cnt++;
  //cout << M << '\n';
  if (calls_cnt > CALLS_CNT_LIMIT)
    quit("Too many calls");
  if (M >= P[0] || M < P[N - 1])
    quit("Invalid argument");

  std::vector<int> L;
  long long R = M;
  for (int i = 0; i < N; i++) {
    if (R >= P[i]) {
      R -= P[i];
      Q[i]++;
      L.push_back(i);
    }
  }
  return {L, R};
}*/



void buy_souvenirs(int n, long long int P0){

    ll tot[n];
    vi calls[n];
    ll vals[n];
    tot[0] = P0;
    calls[0].pb(0);
    vals[0] = P0;
    //cout << n << " " << P0 << '\n';
    //return;
    for (int i = n-1; i > 0; i--){
        
        while (sz(calls[i]) == 0){     
        
            int idx = i;
            for (; idx > 0; idx--) if (sz(calls[idx]) > 0) break;

            ll add = 0;
            ll mul = 0;
            for (int j : calls[idx]){
                if (j > i) add += vals[j];
                else add += i-j, mul++;
            }
            ll up = (tot[idx] - add) / mul;
            //cout << i << " - " << idx << " " << add << "," << mul << " " << up << '\n';
            pair<vi, ll> res = transaction(up);
            assert(sz(res.f) > 0);
            assert(res.f[0] > idx);
            for (int j : res.f) calls[res.f[0]].pb(j);            
            tot[res.f[0]] = up - res.s;
            //for (int j : res.f) cout << j << " ";
            //cout << " - " << sz(calls[i]) << "\n";
        }
        ll temp = tot[i];
        for (int j : calls[i]) if (j > i) temp -= vals[j];
        vals[i] = temp;
    }

    int cnts[n];
    memset(cnts,0,sizeof(cnts));
    for (int i = 0; i < n; i++) for (int j : calls[i]) cnts[j]++;
    for (int i = 0; i < n; i++) while (cnts[i] < i) transaction(vals[i]), cnts[i]++;
}



/*
int main() {
  assert(1 == scanf("%d", &N));
  P.resize(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%lld", &P[i]));
  fclose(stdin);

  Q.assign(N, 0);
  calls_cnt = 0;
  buy_souvenirs(N, P[0]);
  for (int i = 0; i < N; i++)
    printf("%s%d", i ? " " : "", Q[i]);
  printf("\n");
  fclose(stdout);

  return 0;
}
*/

• 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