Submission #1250340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250340		ogkostya	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	12 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <stack>

int count[111];
long long price[111];

std::pair<std::vector<int>, long long> transaction2(long long M)
{
  std::pair<std::vector<int>, long long> res = transaction(M);
  for (int i = 0; i < res.first.size(); i++)
  {
    count[res.first[i]]++;
  }
  res.second = M - res.second;
  return res;
}

void buy_souvenirs(int N, long long P0)
{
  std::pair<std::vector<int>, long long> res;
  if (N == 2)
  {
    res = transaction(P0 - 1);
  }
  else if (N == 3)
  {
    res = transaction(P0 - 1);
    if (res.first.size() == 1)
    {
      long long p1 = P0 - 1 - res.second;
      res = transaction(p1 - 1);
      res = transaction(p1 - 1);
    }
    else
    {
      long long half = (P0 - 1 - res.second) / 2;
      res = transaction(half);
    }
  }
  else if (P0 == N)
  {
    for (int i = 1; i < N; i++)
    {
      for (int j = 1; j <= N - i; j++)
      {
        res = transaction(i);
      }
    }
  }
  else
  {
    std::fill(count, count + N, 0);
    std::fill(price, price + N, 0);

    std::stack<std::pair<std::vector<int>, long long>> st;
    st.push(transaction2(P0 - 1));
    while (st.size() > 0)
    {
      res = st.top();
      if (res.first.size() == 1)
      {
        price[res.first[0]] = res.second;
        st.pop();

        bool all = true;
        for (int i = res.first[0]; i < N; i++)
        {
          if (price[i] == 0)
          {
            all = false;
            break;
          }
        }
        if (!all)
        {
          st.push(transaction2(res.second - 1));
        }
      }
      else
      {
        long long sum = res.second;
        int count = 0;
        for (int i = 0; i < res.first.size(); i++)
        {
          if (price[res.first[i]] != 0)
          {
            sum -= price[res.first[i]];
          }
          else
          {
            count++;
          }
        }
        if (count == 0)
        {
          st.pop();
        }
        else if (count == 1)
        {
          for (int i = 0; i < res.first.size(); i++)
          {
            if (price[res.first[i]] == 0)
            {
              price[res.first[i]] = sum;
              break;
            }
          }
          st.pop();
        }
        else
        {
          st.push(transaction2(sum / count));
        }
      }

      if (st.size() == 0)
      {
        for (int i = N - 2; i > 0; i--)
        {
          if (price[i] != 0 && price[i + 1] == 0)
          {
            st.push(transaction2(price[i] - 1));
            break;
          }
        }
      }
    }

    for (int i = 1; i < N; i++)
    {
      while (count[i] < i)
        transaction2(price[i]);
    }
  }
}

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