Submission #1254049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254049		raphaelp	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	412 KiB

souvenirs

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

struct Query
{
  long long val;
  vector<int> id;
};
vector<Query> Tab;

void review(long long x, vector<long long> &price, vector<long long> &atmost, long long targ)
{
  while (!Tab[x].id.empty() && Tab[x].id.back() > targ)
  {
    Tab[x].val -= price[Tab[x].id.back()];
    Tab[x].id.pop_back();
  }
  if (Tab[x].id.empty())return;
  if (Tab[x].id.size() == 1)
    price[Tab[x].id.back()] = Tab[x].val;
  else
    atmost[Tab[x].id.back()] = Tab[x].val / Tab[x].id.size();
}

void buy_souvenirs(int N, long long P0)
{
  vector<long long> cnt(N), price(N, -1), atmost(N, -1);

  int targ = N - 1, cur = 0, until = 1;
  while (targ >= until)
  {
    while (price[targ] == -1)
    {
      long long ask = price[cur] - 1;
      if (price[cur] == -1)
        ask = atmost[cur];

      pair<vector<int>, long long> temp = transaction(ask);
      Tab.push_back({ask - temp.second, temp.first});
      for (long long i = 0; i < Tab.back().id.size(); i++)
        cnt[Tab.back().id[i]]++;
      review(Tab.size() - 1, price, atmost, targ);
      cur = Tab.back().id.back();
    }
    while (until < N && cnt[until] == until)
      until++;
    targ--;
    cur = 0;
    for (long long i = 0; i < Tab.size(); i++)
    {
      review(i, price, atmost, targ);
      if (Tab[i].id.empty())
      {
        swap(Tab[i], Tab.back());
        Tab.pop_back();
        i--;
        continue;
      }
      cur = max(cur, Tab[i].id.back());
    }
  }
  for (long long i = 0; i < N; i++)
  {
    while (cnt[i] < i)
    {
      transaction(price[i]);
      cnt[i]++;
    }
  }
}

• 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