Submission #1249510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249510		jerry	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	11 ms	400 KiB

souvenirs

#include "souvenirs.h"

#include <set>
#include <utility>
#include <vector>

long long p[105];
int own[105];

void recurse(std::vector<int> items, long long price, int n) {
  while (true) {
    long long known_price = 0;
    std::set<int> unknown(items.begin(), items.end());
    for (int i : items) {
      if (p[i]) {
        known_price += p[i];
        unknown.erase(i);
      }
    }

    if (unknown.size() == 0) {
      return;
    }
    if (unknown.size() == 1) {
      p[*unknown.begin()] = price - known_price;
      if (*unknown.begin() == n - 1) {
        return;
      }
    }

    const long long query = (price - known_price - 1) / unknown.size();
    const auto& [received, change] = transaction(query);
    for (int i : received) {
      own[i]++;
    }
    recurse(received, query - change, n);
  }
}

void buy_souvenirs(int n, long long p0) {
  for (int i = 0; i < n; i++) {
    p[i] = 0;
    own[i] = 0;
  }
  recurse({0}, p0, n);
  for (int i = 0; i < n; i++) {
    while (own[i] != i) {
      transaction(p[i]);
      own[i]++;
    }
  }
}

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