제출 #1310201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310201		kunzaZa183	선물 (IOI25_souvenirs)	C++20	100 / 100	13 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void buy_souvenirs(int N, long long P0) {
  vector<int> times(N);
  vector<pair<vector<int>, ll>> vpv(N, {{}, -1});
  vpv[0] = {{}, P0};

  auto ask = [&](ll x) {
    auto smt = transaction(x);
    for (auto a : smt.first)
      times[a]++;
    vpv[smt.first[0]] = {smt.first, x - smt.second};
    vpv[smt.first[0]].first.erase(vpv[smt.first[0]].first.begin());
  };

  while (1) {

    for (int i = 1; i < N; i++) {
      if (vpv[i].first.empty() && vpv[i].second == -1 &&
          vpv[i - 1].first.empty() && vpv[i - 1].second != -1) {
        ask(vpv[i - 1].second - 1);
      }
    }

    for (int i = 0; i < N; i++) {
      if (vpv[i].first.empty())
        continue;
      for (int j = vpv[i].first.size() - 1; j >= 0; j--) {
        if (vpv[vpv[i].first[j]].first.empty() &&
            vpv[vpv[i].first[j]].second != -1) {
          vpv[i].second -= vpv[vpv[i].first[j]].second;
          vpv[i].first.erase(vpv[i].first.begin() + j);
        }
      }

      if (vpv[i].first.empty())
        continue;

      for (int j = i + 1; j <= vpv[i].first.back(); j++) {
        if (vpv[j].second != -1) {
          goto A;
        }
      }
      ask(vpv[i].second / (vpv[i].first.size() + 1));
    A:;
    }

    for (int i = 0; i < N; i++) {
      if (vpv[i].second == -1 || !vpv[i].first.empty()) {
        goto B;
      }
    }
    break;
  B:;
  }

  for (int i = 0; i < N; i++) {
    while (i != times[i])
      ask(vpv[i].second);
  }
}

• 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