Submission #1249452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249452		_is_this_fft_	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <vector>
#include <cassert>

using namespace std;

typedef long long ll;

struct Row {
  vector<int> present;
  ll sum;

  Row () { }
  
  Row (int _n, vector<int> _items, ll _sum) : present(_n, 0), sum(_sum) {
    for (int u : _items) {
      present[u] = 1;
    }
  }

  int count () {
    int ans = 0;
    for (int u : present)
      ans += u;
    return ans;
  }

  bool exists () {
    return !present.empty();
  }

  void operator-= (const Row& other) {
    for (int i = 0; i < (int) present.size(); i++)
      present[i] -= other.present[i];

    sum -= other.sum;
  }
};

void reduce_and_insert (vector<Row> &lead, Row &row) {
  int n = lead.size();
  
  for (int j = 0; j < n; j++) {
    if (lead[j].exists() && lead[j].count() == 1 && row.present[j]) {
      row -= lead[j];
    }
  }

  int nk = -1;
  for (int j = 0; j < n; j++) {
    if (row.present[j]) {
      nk = j;
      break;
    }
  }

  assert(nk != -1);
  assert(!lead[nk].exists());

  lead[nk] = row;
}

pair<vector<int>, ll> transaction_wrap (ll m, vector<int> &bought) {
  auto pr = transaction(m);
  for (int u : pr.first)
    bought[u]++;
  return pr;
}

void buy_souvenirs (int n, ll p0) {
  vector<Row> lead (n);
  vector<int> bought (n, 0);
  
  ll nxt = p0 - 1;
  while (true) {
    auto pr = transaction_wrap(nxt, bought);
    Row row (n, pr.first, nxt - pr.second);
    lead[pr.first[0]] = row;

    if (pr.first.size() == 1) {
      nxt = row.sum - 1;
    } else {
      nxt = row.sum / pr.first.size();
    }

    if (pr.first.size() == 1 && pr.first[0] == n - 1) {
      break;
    }
  }

  // initialization is complete
  while (true) {
    // pseudo-Gaussian elimination
    for (int i = n - 1; i >= 0; i--) {
      if (!lead[i].exists() || lead[i].count() != 1)
        continue;

      for (int j = i - 1; j >= 0; j--) {
        if (lead[j].exists() && lead[j].present[i]) {
          lead[j] -= lead[i];
        }
      }
    }

    // if everyone has a lead, then we are done
    bool finished = true;
    for (int i = 1; i < n; i++) {
      if (!lead[i].exists())
        finished = false;
    }

    if (finished)
      break;

    bool ee = false;
    for (int i = n - 1; i >= 0; i--) {
      if (!lead[i].exists())
        ee = true;
      
      if (lead[i].exists() && lead[i].count() > 1) {
        ll ask = lead[i].sum / lead[i].count();
        auto pr = transaction_wrap(ask, bought);
        Row row (n, pr.first, ask - pr.second);
        reduce_and_insert(lead, row);
        
        break;
      }

      if (lead[i].exists() && lead[i].count() == 1 && ee) {
        ll ask = lead[i].sum - 1;
        auto pr = transaction_wrap(ask, bought);
        Row row (n, pr.first, ask - pr.second);
        reduce_and_insert(lead, row);

        break;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    while (bought[i] < i) {
      transaction_wrap(lead[i].sum, bought);
    }
  }
}

• 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