제출 #1251183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251183		Clan328	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

struct Entry {
  pair<vector<int>, long long> ans;
  int count;
  long long price;
};

void buy_souvenirs(int N, long long P0) {
  // std::pair<std::vector<int>, long long> res = transaction(3);
  vector<long long> res(N);
  vector<int> curr(N);
  res[0] = P0;

  int cnt = 1;

  stack<Entry> st;

  long long price = res[0]-1;
  while (cnt < N) {
    cout << price << endl;
    pair<vector<int>, long long> ans = transaction(price);

    int count = ans.first.size();
    for (int i = 0; i < count; i++) {
      curr[ans.first[i]]++;
    }

    if (count == 1) {
      res[ans.first[0]] = price - ans.second;
      cnt++;

      bool down = false;
      for (int i = ans.first[0]+1; i < N; i++) down |= res[ans.first[0]] == 0;

      if (down) price = res[ans.first[0]]-1;
      else {
        bool found = false;
        while (st.size() && !found) {
          Entry entry = st.top(); st.pop();

          int tmpCount = 0, tmpSum = 0;
          for (int i = 0; i < entry.count; i++) {
            // if (entry.ans.first[i] == 0) continue;
            if (res[entry.ans.first[i]] != 0) {
              tmpSum += res[entry.ans.first[i]];
              continue;
            }
            tmpCount++;
          }

          if (tmpCount == 1) {
            for (int i = 0; i < entry.count; i++) {
              if (res[entry.ans.first[i]] == 0) continue;
              res[entry.ans.first[i]] = entry.price-entry.ans.second-tmpSum;
              cnt++;
            }
          }

          long long tmpPrice = entry.price-entry.ans.second;
          int idx = entry.count-1;
          for (int i = N-1; i >= 0 && idx >= 0; i--) {
            if (entry.ans.first[idx] != i) break;
            if (res[i] == 0) break;
            tmpPrice -= res[entry.ans.first[i]];
            idx--;
          }

          if (tmpPrice != 0) {
            price = tmpPrice;
            found = true;
          }
        }

        if (!found) {
          for (int i = N-2; i >= 0; i--) {
            if (res[i+1] == 0 && res[i] != 0) {
              price = res[i]-1;
              break;
            }
          }
        }
      }
    } else {
      st.push({ans, count, price});
      price = (price - ans.second)/count;
    }
    // cout << res[0] << " " << res[1] << " " << res[2] << endl;
  }

  for (int i = 0; i < N; i++) {
    while (curr[i] < i) {
      curr[i]++;
      transaction(res[i]);
    }
  }

  return;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 4
• Subtask 2: 0 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33