제출 #1251338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251338		jwvg0425	선물 (IOI25_souvenirs)	C++20	67 / 100	19 ms	424 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;
vector<int> firstCheck;

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;
		if (rq[0] < N - 1)
			firstCheck.push_back(rq[0] + 1);
		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;

				if (nq[0] < N - 1)
					firstCheck.push_back(nq[0] + 1);
			}

			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;
	firstCheck.push_back(1);

	// 값 탐색
	while (any_of(values, values + N, [](i64 v) { return v == -1; }))
	{
		// 값 확정 추가하는 쿼리 과정 수행
		sort(all(firstCheck));
		vector<int> nfirstCheck;
		for (auto& f : firstCheck)
		{
			if (values[f] == -1)
				nfirstCheck.push_back(f);
		}
		firstCheck = nfirstCheck;

		if (!firstCheck.empty())
		{
			auto v = firstCheck.back();
			firstCheck.pop_back();
			query(N, values[v - 1] - 1);
		}
		else
		{
			sort(all(queries), [](auto& l, auto& r) { return l.xx.size() < r.xx.size(); });
			query(N, queries[0].yy / queries[0].xx.size());
		}


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

	// 구매 횟수 모자란 거 구매
	while (!buyOk(N))
	{
		bool ok = false;
		for (int i = 1; i < N; i++)
		{
			if (buyCount[i] == i)
				continue;

			for (int j = i + 1; j < N; j++)
			{
				if (buyCount[j] == j)
					continue;

				i64 p = values[i] + values[j];
				if (p >= values[i - 1])
					continue;

				transaction(p);
				buyCount[i] += 1;
				buyCount[j] += 1;
				ok = true;
				break;
			}

			if (ok)
				break;
		}

		if (!ok)
		{
			for (int i = 1; i < N; i++)
			{
				if (buyCount[i] == i)
					continue;

				buyCount[i] += 1;
				transaction(values[i]);
				break;
			}
		}
	}
}

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