Submission #1251418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251418		jwvg0425	Souvenirs (IOI25_souvenirs)	C++20	Compilation error	0 ms	0 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;
set<i64> used;

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)
{
	used.insert(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(); });
			for (auto& [q, s] : queries)
			{
				if (used.find(s) != used.end())
					continue;
				query(N, s / q.size());
				break;
			}
		}


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

	check();

	// 구매 횟수 모자란 거 구매
	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;
			}
		}
	}
}

Compilation message (stderr)

souvenirs.cpp: In function 'void buy_souvenirs(int, i64)':
souvenirs.cpp:172:9: error: 'check' was not declared in this scope
  172 |         check();
      |         ^~~~~