Submission #1253793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253793		nicolo_010	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	1083 ms	412 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++;
    }
  }
  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) {
    while(1) {
      if (!deduce()) break;
    }
    ll last = P0-1; 
    rep(i, 1, N) {
      cerr << i << endl;
      if (beg[i] == false && val[i] == -1 && val[i-1] != -1) {
        ll last = val[i-1]-1;
        int ni;
        while (true) {
          auto aux = transaction(last);
          ni = aux.first[0];
          cerr << ni << " " << aux.first.size() << endl;
          beg[i] = true;
          set<int> s;
          for (auto x : aux.first) {
            s.insert(x);
            am[x]++;
          }
          cerr << "DEGUB" << endl;
          sets[ni] = s;
          sums[ni] = last-aux.second;
          last = (sums[ni]/aux.first.size());
          if (aux.first.size() == 1) break;
        }
      }
    }
  }
  rep(i, 0, N) {
    rep(j, 0, i-am[i]) {
      transaction(val[i]);
    }
  }
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33