Submission #1253291

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

souvenirs

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

using namespace std;

void buy_souvenirs(int N, long long P0) {
  vector<int> counts(N);
  vector<long long> values(N);
  unordered_set<long long> bounds;
  vector<long long> cands;
  vector<vector<long long>> rels;
  values[0] = P0;
  for (int i = 1; i < N; i++) values[i] = -1;
  while (true) {
    // for (long long i : values) {
    //   cout << i << " ";
    // }
    // cout << endl;
    bool done = true;
    for (long long i : values) {
      if (i == -1) {
        done = false;
        break;
      }
    }
    if (done) break;
    long long bound = -1;
    bool start = false;
    int culprit = -1;
    for (int i  = N - 1; i >= 0; i--) {
      if (values[i] == -1) {
        if (!start) culprit = i;
        start = true;
      }
      else if (start) {
        bound = values[i];
        break;
      }
    }
    //cout << bound << " " << culprit << endl;
    if (cands.size() == 0) cands.push_back(bound);
    while (cands.size() > 0) {
      for (long long i : values) {
        //cout << i << " ";
      }
      //cout << endl;
      bound = cands[0];
      //cout << "lol " << cands[0] << endl;
      cands.erase(cands.begin());
      if (bounds.find(bound) != bounds.end()) continue;
      bounds.insert(bound);
      pair<vector<int>, long long> x = transaction(bound - 1);
      vector<long long> temp;
      long long y = 0;
      for (int i : x.first) {
        counts[i]++;
        if (values[i] == -1) {
          temp.push_back(i);
        }
        else {
          y += values[i];
        }
      }
      long long off = 0;
      for (int i : temp) {
        off += temp[temp.size() - 1] - i;
      }
      temp.push_back(bound - 1 - x.second - y);
      rels.push_back(temp);
      if (temp.size() == 2) {
        values[temp[0]] = temp[1];
        bound = temp[1];
        if (temp[0] == culprit) break;
      }
      else {
        bound = (temp[temp.size() - 1] - off) / (temp.size() - 1) + 1;
        //cout << "bound " << bound << " " << off << " ! ";
       //for (long long i : temp) cout << i << " ";
        //cout << endl;
      }
      cands.push_back(bound);
    }
    bool stop = false;
    while (!stop) {
      stop = true;
      for (int i = 0; i < rels.size(); i++) {
        bool sdf = false;
        int target = -1;
        int count = 0;
        //cout << "here ";
        for (int j = 0; j < rels[i].size() - 1; j++) {
          //cout << rels[i][j] << " ";
          if (values[rels[i][j]] != -1) {
            rels[i][rels[i].size() - 1] -= values[rels[i][j]];
            rels[i].erase(rels[i].begin() + j);
            j--;
          }
          else {
            target = rels[i][j];
          }
        }
        //cout << endl;
        //cout << "target " << target;
        if (rels[i].size() == 2) {
          values[target] = rels[i][rels[i].size() - 1];
          //cout << "before " << rels[i][rels[i].size() - 1] << endl;
          stop = false;
          rels.erase(rels.begin() + i);
          i--;
        }
        else if (rels[i].size() == 1) {
          rels.erase(rels.begin() + i);
          i--;
        }
        else {
          long long r = 0;
          for (int j = 0; j < rels[i].size() - 1; j++) {
            r += rels[i][rels[i].size() - 2] - rels[i][j];
          }
          long long test = (rels[i][rels[i].size() - 1] - r) / (rels[i].size() - 1) + 1;
          //cout << "test " << test << endl;
          if (bounds.find(test) == bounds.end()) {
            cands.push_back(test);
            sdf = true;
            break;
          }
        }
        if (sdf) {
          stop = true;
          break;
        }
      }
    }
  }
  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: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33