제출 #1251265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251265		fadyscube	선물 (IOI25_souvenirs)	C++20	25 / 100	12 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 i = 0; i < t.first.size(); i++) reps[t.first[i]]++;
  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 i = 0; i < t.first.size(); i++) reps[t.first[i]]++;
    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 = 2; i < N-1; i++) {
    if (p[i] != -1) {
      t = transaction(p[i]-1);
      for (int i = 0; i < t.first.size(); i++) reps[t.first[i]]++;
      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++) {
      transaction(p[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