Submission #1253804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253804		nicolo_010	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cerr if (0) cerr

v<set<int>> sets;
v<ll> sums;
v<ll> val; 
v<bool> beg;
v<int> am;
int remaining;

int deduce() {
  int N = sums.size();
  int cnt=0;
  rep(i, 0, N) {
    cerr << i << endl;
    set<int> aux = sets[i];
    for (auto y : sets[i]) {
      if (val[y] != -1) {
        aux.erase(y);
        sums[i] -= val[y];
      }
    }
    sets[i] = aux;
  }
  rep(i, 0, N) {
    if (sets[i].size() == 1) {
      val[i] = sums[i];
      cnt++;
      sets[i].clear();
    }
  }
  remaining -= cnt;
  return cnt;
}

void buy_souvenirs(int N, long long P0) {
  remaining = N-1;
  sets.resize(N);
  val.assign(N, -1);
  sums.assign(N, -1);
  beg.assign(N, false);
  am.assign(N, 0);
  beg[0] = true;
  val[0] = P0;
  sums[0] = P0;
  while (remaining > 0) {
    cerr << remaining << endl;
    while(1) {
      if (!deduce()) break;
    }
    if (remaining == 0) break;
    bool havetoguess = false;
    for (int i = N-1; i >= 0; i--) {
      cerr << i << " " << havetoguess << endl;
      if (val[i] == -1) havetoguess = true;
      if (val[i] != -1 && havetoguess) {
          auto aux = transaction(val[i]-1);
          set<int> s;
          for (auto x : aux.first) {
            s.insert(x);
            am[x]++;
          }
          sums[i+1] = (val[i]-1) - aux.second;
          sets[i+1] = s;
          break;
      }
      if (sets[i].size()) {
        ll x = sums[i] / (int)sets[i].size();
        auto aux = transaction(x);
        set<int> s;
        for (auto x : aux.first) {
          am[x]++;
          s.insert(x);
        }
        int k = aux.first[0];
        sets[k] = s;
        sums[k] = x-aux.second;
        break;
      }
    }
  }
  rep(i, 0, N) {
    while (am[i] < i) {
      transaction(val[i]);
      am[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