제출 #1249907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249907		_abaatar	선물 (IOI25_souvenirs)	C++20	4 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
using namespace std;

const int Ma = 5e2 + 10;
using ll = long long;
int sold[111];

void buy_souvenirs(int N, long long P0)
{
  for (int i = 1; i < N; i++)
    sold[i] = i;

  ll hi = P0;

  auto ress = transaction(hi - 1);
  for (auto x : ress.first)
    sold[x]--;

  hi -= 1;

  for (int i = 2; i < N; i++)
  {
    hi = hi >> 1;
    while (sold[i] > 0)
    {
      auto res = transaction(hi);

      for (auto x : res.first)
      {
        sold[x]--;
      }
    }

    // hi = hi >> 1;

    // P[i] --g olchuul hi = (P[i] - 1) << 1 geed duuslaa
  }
  return;

  for (int i = 1; i < N; i++)
    sold[i] = i;

  ll cur = P0 - 1;
  bool hasOne = false;

  for (int i = 1; i < N; i++)
  {
    if (i == N - 1 && hasOne == true)
    {
      while (sold[N - 1]-- > 0)
        transaction(1);
      return;
    }

    auto res = transaction(cur);
    sold[i]--;
    if (res.second == 1)
    { // no price 1 and p[i] = p[i - 1] - 2
      while (sold[i]-- > 0)
      {
        transaction(cur - 1);
      }
      cur -= 2;
    }
    else
    { // res.second = 0
      if (res.first.size() == 1)
      { // p[i] = p[i - 1] - 1
        while (sold[i]-- > 0)
        {
          transaction(cur);
        }
        cur -= 1;
      }
      else
      { // p[i] = p[i - 1] - 2 and hasOne = true
        hasOne = true;
        sold[N - 1]--;
        while (sold[i]-- > 0)
        {
          transaction(cur - 1);
        }
        cur -= 2;
      }
    }
  }
}

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