Submission #1251323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251323		jwvg0425	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

// -1 이면 아직 안 밝혀진 값
int buyCount[105];
i64 values[105];

// (안 밝혀진 원소, 원소 전체 합)으로만 이루어진 쿼리
vector<pair<vector<int>, i64>> queries;

bool buyOk(int N)
{
	for (int i = 0; i < N; i++)
	{
		if (buyCount[i] != i)
			return false;
	}

	return true;
}

// v로 쿼리 - 확정 안 된 목록에서 x/k 재귀 반복, k=1일 때 확정짓고 종료
void query(int N, i64 v)
{
	auto [ls, rem] = transaction(v);
	i64 s = v - rem;
	vector<int> rq;
	for (auto& a : ls)
	{
		buyCount[a]++;
		if (values[a] != -1)
			s -= values[a];
		else
			rq.push_back(a);
	}

	if (rq.empty())
		return;

	if (rq.size() == 1)
	{
		values[rq[0]] = s;
		return;
	}

	queries.emplace_back(rq, s);

	i64 nq = s / rq.size();

	query(N, nq);
}

void reduce(int N)
{
	while (true)
	{
		bool hasUpdate = false;
		for (auto& [q, s] : queries)
		{
			vector<int> nq;
			i64 ns = s;

			for (auto& qi : q)
			{
				if (values[qi] != -1)
					ns -= values[qi];
				else
					nq.push_back(qi);
			}

			if (ns != s)
				hasUpdate = true;

			if (nq.size() == 1)
				values[nq[0]] = ns;

			q = nq;
			s = ns;
		}

		vector<pair<vector<int>, i64>> nqueries;
		for (auto& [q, s] : queries)
		{
			if (q.size() >= 2)
				nqueries.emplace_back(q, s);
		}

		queries = nqueries;

		if (!hasUpdate)
			break;
	}
}

void buy_souvenirs(int N, i64 P0) {
  memset(values, -1, sizeof(values));

  values[0] = P0;

  // 값 탐색
  while (any_of(values, values + N, [](i64 v) { return v == -1; }))
  {
	  // 값 확정 추가하는 쿼리 과정 수행
	  for (int i = N - 2; i >= 0; i--)
	  {
		  if (values[i] != -1 && values[i + 1] == -1)
		  {
			  query(N, values[i] - 1);
			  break;
		  }
	  }

	  // 확정된 값을 기반으로 queries 갱신하는 작업 수행
	  reduce(N);
  }

  // 구매 횟수 모자란 거 구매
  while (!buyOk(N))
  {
	  int st = 0;
	  for (int i = 0; i < N; i++)
	  {
		  if (buyCount[i] != i)
		  {
			  transaction(values[i]);
			  buyCount[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