Submission #1250639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250639		gangsterveggies	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	408 KiB

souvenirs

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

using namespace std;

long long simplify_equation(vector<int> &equation, vector<long long> &P) {
  long long sum_removed = 0;
  vector<int> new_equation;

  for (int index : equation) {
    if (P[index] != -1) {
      sum_removed += P[index];
    } else {
      new_equation.push_back(index);
    }
  }

  equation = std::move(new_equation);
  return sum_removed;
}

void buy_souvenirs(int N, long long P0) {
  int len = 1;
  vector<long long> P(N);
  P.assign(N, -1);
  P[0] = P0;

  vector<int> calls(N);
  calls.assign(N, 0);

  vector<pair<long long, pair<vector<int>, long long>>> equations;

  while (1) {
    int smallest_index = -1, missing = 0;
    for (int i = N - 1; i >= 0; i--) {
      if (P[i] != -1 && missing && smallest_index == -1)
        smallest_index = i;
      if (P[i] == -1)
        missing = 1;
    }

    if (!missing) {
      break;
    }

    int updated = 0;
    for (auto it = equations.begin(); it != equations.end();) {
      long long sum_removed = simplify_equation(it->second.first, P);
      it->second.second += sum_removed;

      if (it->second.first.size() == 0) {
        it = equations.erase(it);
      } else if (it->second.first.size() == 1) {
        P[it->second.first[0]] = it->first - it->second.second;
        it = equations.erase(it);
        updated = 1;
      } else {
        ++it;
      }
    }

    if (updated) {
      continue;
    }

    pair<long long, pair<vector<int>, long long>>* smallest_eq = nullptr;
    for (auto& eq : equations) {
      if (!smallest_eq || *min_element(eq.second.first.begin(), eq.second.first.end()) >
                  *min_element(smallest_eq->second.first.begin(), smallest_eq->second.first.end())) {
        smallest_eq = &eq;
      }
    }

    int smallest_eq_index = -1;
    if (smallest_eq) {
      smallest_eq_index = *min_element(smallest_eq->second.first.begin(), smallest_eq->second.first.end());
    }

    if (smallest_index > smallest_eq_index) {
      pair<vector<int>, long long> new_eq = transaction(P[smallest_index] - 1);
      for (auto & index : new_eq.first) {
        calls[index]++;
      }
      //printf("Transaction for index %d with value %lld\n", smallest_index, P[smallest_index] - 1);
      //for (int index : new_eq.first) {
      //  printf("%d ", index);
      //}
      //printf(" - %lld\n", new_eq.second);
      equations.push_back(make_pair(P[smallest_index] - 1,  new_eq));
    }
    else {
      long long value = (smallest_eq->first - smallest_eq->second.second) / 
                        smallest_eq->second.first.size();
      //printf("Transaction for value %lld with size %zu (%d)\n", value, smallest_eq->second.first.size(), smallest_eq_index);
      //for (int index : smallest_eq->second.first) {
      //  printf("%d ", index);
      //}
      //printf("\n");
      pair<vector<int>, long long> new_eq = transaction(value);
      for (auto & index : new_eq.first) {
        calls[index]++;
      }
      //for (int index : new_eq.first) {
      //  printf("%d ", index);
      //}
      //printf(" - %lld\n", new_eq.second);
      equations.push_back(make_pair(value, new_eq));
    }
  }

  for (int i = 0; i < N; i++) {
    while (calls[i] != i) {
      transaction(P[i]);
      calls[i]++;
    }
  }

  return;
}

• 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