Submission #1250338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250338		Wayne_Yan	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct dat {
  vector<int> counts;
  ll total_price;
  bool operator<(const dat &b) {
    return lexicographical_compare(counts.begin(), counts.end(),
                                   b.counts.begin(), b.counts.end());
  }

  void reduce(dat d) {
    assert(d.counts.size() == 1);
    for (int i = 0; i < (int)counts.size(); i++) {
      if (counts[i] == d.counts[0]) {
        total_price -= d.total_price;
        counts.erase(counts.begin() + i);
        break;
      }
    }
  }
};

void buy_souvenirs(int n, long long p0) {
  vector<int> count(n);
  vector<dat> st;
  vector<dat> done;
  vector<ll> ans(n);

  auto calc_next_transaction = [&](dat x) {
    int fst = x.counts[0];
    int lst = x.counts[x.counts.size() - 1];
    for (int i = lst - 1; i > fst; i--) {
      if (ans[i] != 0)
        return ans[i] - 1;
    }
    return (x.total_price - 1) / (int)x.counts.size();
  };

  auto get_dat = [&](ll x) {
    auto [v, rest] = transaction(x);
    for (int i : v)
      count[i]++;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
      if (ans[v[i]] != 0) {
        rest += ans[v[i]];
        v.erase(v.begin() + i);
      }
    }
    dat res;
    res.counts = v;
    res.total_price = x - rest;
    return res;
  };

  ans[0] = p0;

  while (true) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
      if (ans[i] == 0) {
        idx = i;
        break;
      }
    }
    if (idx == -1)
      break;

    auto process = [&](ll x) {
      st.push_back(get_dat(x));
      for (int i = (int)st.size() - 1; i >= 0; i--) {
        if (st[i].counts.size() == 1) {
          ans[st[i].counts[0]] = st[i].total_price;
          done.push_back(st[i]);
          st.erase(st.begin() + i);
        }
      }
      while (!done.empty()) {
        auto d = done.back();
        done.pop_back();
        for (int i = (int)st.size() - 1; i >= 0; i--) {
          st[i].reduce(d);
          if (st[i].counts.size() == 1) {
            ans[st[i].counts[0]] = st[i].total_price;
            done.push_back(st[i]);
            st.erase(st.begin() + i);
          }
        }
      }
    };

    process(ans[idx - 1] - 1);

    while (!st.empty()) {
      sort(st.rbegin(), st.rend());
      auto fst = st[0];
      ll next_transaction = calc_next_transaction(fst);
      process(next_transaction);
    }
  }

  for (int i = 1; i < n; i++) {
    while (count[i] < i) {
      transaction(ans[i]);
      count[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