Submission #1251210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251210		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) {
    pair<vector<int>, long long> ans = transaction(price);

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

    int newCount = count, lastN = -1;
    long long tmpSum2 = 0;
    for (int i = 0; i < count; i++) {
      if (res[ans.first[i]] == 0)
        lastN = ans.first[i];
      else {
        tmpSum2 += res[ans.first[i]];
        newCount--;
      }
    }

    cout << price << " " << count << " " << newCount << endl;

    if (newCount <= 1) {
      if (newCount == 1) {
        res[lastN] = price - ans.second-tmpSum2;
        cnt++;
      }

      long long down = -1;
      for (int i = ans.first[0]+1; i < N; i++) {
        if (res[i] == 0) {
          down = res[i-1]-1;
          break;
        }
      }
      // cout << res[ans.first[0]] << endl;
      // cout << tmpSum2 << " " << ans.second << endl;
      if (down != -1) price = down;
      else {
        bool found = false;
        while (st.size() && !found) {
          Entry entry = st.top(); st.pop();

          long long 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++;
          }
          // cout << "HI2: " << entry.price-entry.ans.second-tmpSum << endl;
          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[idx]];
            idx--;
          }

          if (tmpPrice != 0) {
            price = tmpPrice;
            found = true;
            // cout << "HI: " << res[9] << endl;
          }
        }

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