Submission #1251291

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

souvenirs

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

using namespace std;

void buy_souvenirs(int N, long long P0) {
  vector<long long> p(N, -1);
  vector<long long> reps(N, 0);
  p[0] = P0;
  long long mon = P0 - 1;
  pair<vector<int>, long long> t = transaction(mon);
  for (int l = 0; l < t.first.size(); l++) reps[t.first[l]]++;
  vector<pair<vector<int>, long long>> eq;
  eq.push_back({t.first, mon - t.second});
  
  for (int i = 0; i < N; i++) {
    mon = (mon - t.second) / (t.first.size());
    if (mon == 2) break;
    if (t.first.size() == 1) {
      if (t.first[0] == N-1) break;
      t = transaction(mon-1);
      mon = mon - 1;
    } else {
      t = transaction(mon);
    }
    
    for (int l = 0; l < t.first.size(); l++) reps[t.first[l]]++;
    eq.push_back({t.first, mon - t.second});
  }
  
  sort(eq.begin(), eq.end(), [](auto const &a, auto const &b) {
    return a.first.size() < b.first.size();
  });
  
  for (auto pa: eq) {
    vector<int> els = pa.first;
    long long others = 0;
    int k = 0;
    for (auto i: els) {
      if (p[i] != -1) {
        others += p[i];
        k++;
      }
    }
    if (k+1 == els.size()) {
      for (auto i: els) {
        if (p[i] == -1) {
          p[i] = pa.second - others;
        }
      }
    }
  }

  for (int i = 1; i < N-1; i++) {
    if (p[i] != -1) {
      t = transaction(p[i]-1);
      for (int l = 0; l < t.first.size(); l++) reps[t.first[l]]++;
      eq.push_back({t.first, p[i]-1-t.second});
    }
  }

  sort(eq.begin(), eq.end(), [](auto const &a, auto const &b) {
    return a.first.size() < b.first.size();
  });
  
  for (auto pa: eq) {
    vector<int> els = pa.first;
    long long others = 0;
    int k = 0;
    for (auto i: els) {
      if (p[i] != -1) {
        others += p[i];
        k++;
      }
    }
    if (k+1 == els.size()) {
      for (auto i: els) {
        if (p[i] == -1) {
          p[i] = pa.second - others;
        }
      }
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = reps[i]; j < i; j++) {
      if (p[i] != -1)
        transaction(p[i]);
    }
  }
  
  return;
}

• 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