Submission #1253274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253274		powervic08	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	13 ms	400 KiB

souvenirs

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

using namespace std;

void buy_souvenirs(int N, long long P0) {
  vector<int> counts(N);
  vector<long long> values(N);
  values[0] = P0;
  for (int i = 1; i < N; i++) values[i] = -1;
  while (true) {
    bool done = true;
    for (long long i : values) {
      if (i == -1) {
        done = false;
        break;
      }
    }
    if (done) break;
    long long bound = -1;
    bool start = false;
    for (int i  = N - 1; i >= 0; i--) {
      if (values[i] == -1) start = true;
      else if (start) {
        bound = values[i];
        break;
      }
    }
    vector<vector<long long>> rels;
    while (true) {
      pair<vector<int>, long long> x = transaction(bound - 1);
      vector<long long> temp;
      long long off = 0;
      for (int i : x.first) {
        counts[i]++;
        off += x.first[x.first.size() - 1] - i;
        temp.push_back(i);
      }
      temp.push_back(bound - 1 - x.second);
      rels.push_back(temp);
      if (temp.size() == 2) {
        values[temp[0]] = temp[1];
        bound = temp[1];
        if (temp[0] == N - 1) break;
      }
      else {
        bound = (temp[temp.size() - 1] - off) / x.first.size() + 1;
      }
    }
    bool stop = false;
    while (!stop) {
      stop = true;
      for (int i = 0; i < rels.size(); i++) {
        int count = 0;
        int target = -1;
        long long sum = 0;
        for (int j = 0; j < rels[i].size() - 1; j++) {
          if (values[rels[i][j]] != -1) {
            count++;
            sum += values[rels[i][j]];
          }
          else {
            target = rels[i][j];
          }
        }
        if (count == rels[i].size() - 2) {
          values[target] = rels[i][rels[i].size() - 1] - sum;
          stop = false;
          rels.erase(rels.begin() + i);
          i--;
        }
        else if (count == rels[i].size() - 1) {
          rels.erase(rels.begin() + i);
          i--;
        }
      }
    }
  }
  for (int i = 0; i < N; i++) {
    while (counts[i] < i) {
      transaction(values[i]);
      counts[i]++;
    }
  }
  return;
}

• 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