#194246 (C++14) No.529 帰省ラッシュ

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	tansunogon
提出日時	2017-08-07 01:46:55
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	154 ms / 4,500 ms
コード長	19,442 bytes
コンパイル時間	1,598 ms
コンパイル使用メモリ	92,120 KB
実行使用メモリ	33,944 KB
最終ジャッジ日時	2024-05-09 16:57:47
合計ジャッジ時間	4,571 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	68 ms 23,540 KB
testcase_09	AC	74 ms 23,968 KB
testcase_10	AC	110 ms 28,672 KB
testcase_11	AC	112 ms 28,796 KB
testcase_12	AC	60 ms 20,976 KB
testcase_13	AC	92 ms 33,944 KB
testcase_14	AC	71 ms 27,008 KB
testcase_15	AC	154 ms 28,292 KB
testcase_16	AC	151 ms 28,296 KB
testcase_17	AC	107 ms 31,632 KB
testcase_18	AC	107 ms 31,664 KB
testcase_19	AC	109 ms 31,708 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

In member function 'void SegTree::update(int, int)',
    inlined from 'int Solver::query2(int, int)' at main.cpp:818:36:
main.cpp:65:71: warning: 'group_data_index_max' may be used uninitialized [-Wmaybe-uninitialized]
   65 |                         int value2 = data_[child_begin + (child_index ^ 1)];
      |                                                          ~~~~~~~~~~~~~^~~~
main.cpp: In member function 'int Solver::query2(int, int)':
main.cpp:737:21: note: 'group_data_index_max' was declared here
  737 |                 int group_data_index_max = -1;
      |                     ^~~~~~~~~~~~~~~~~~~~

ソースコード

raw source code

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

#ifdef TIME_MEASURE
#include <chrono>
auto start_time = std::chrono::system_clock::now();
#define TimePrint(message) do { \
		auto end_time = std::chrono::system_clock::now(); \
		auto time_span = end_time - start_time; \
		long long time_ms = std::chrono::duration_cast<std::chrono::milliseconds>(time_span).count(); \
		fprintf(stderr, "%s: %lld\n", message, time_ms); \
		start_time = end_time; \
	} while (false)
#else
#define TimePrint(message) do {} while (false)
#endif

class SegTree
{
public:
	// in the case where n = 5
	//
	// [------6------]
	// [--4--] [--5--]
	// [0] [1] [2] [3] [4]
	std::vector<int> data_;
	std::vector<int> index_;
	const int n_;

	SegTree(size_t n) : n_(n)
	{
		int data_size = 0;
		while (n > 0)
		{
			data_size += n;
			n >>= 1;
		}
		data_ = std::vector<int>(data_size, -1);
		index_ = std::vector<int>(data_size);
		for (int i = 0; i < n_; ++i)
		{
			index_[i] = i;
		}
	}

	void update(int i, int value)
	{
		assert(i >= 0 && i < n_);

		data_[i] = value;
		int index = i;

		int child_begin = 0;
		int child_index = i;
		int parent_begin = n_;
		int parent_size = n_ / 2;
		int parent_index = i / 2;
		while (parent_index < parent_size)
		{
			int value2 = data_[child_begin + (child_index ^ 1)];
			if (value > value2)
			{
				data_[parent_begin + parent_index] = value;
				index_[parent_begin + parent_index] = index;
			}
			else
			{
				data_[parent_begin + parent_index]
					= value
					= value2;
				index_[parent_begin + parent_index]
					= index
					= index_[child_begin + (child_index ^ 1)];
			}

			child_begin = parent_begin;
			child_index = parent_index;
			parent_begin += parent_size;
			parent_size /= 2;
			parent_index /= 2;
		}
	}

	// max [0, i]
	int getmax(int i, int* index) const
	{
		assert(i >= 0 && i < n_);

		int ret_max = -1;
		int index_begin = 0;
		int size = n_;
		while (1)
		{
			if ((i & 1) == 0)
			{
				if (ret_max < data_[index_begin + i])
				{
					ret_max = data_[index_begin + i];
					*index = index_[index_begin + i];
				}
				if (i == 0)
				{
					return ret_max;
				}
				--i;
			}
			index_begin += size;
			size /= 2;
			i /= 2;
		}
	}

	// max [i, j]
	int getmax(int i, int j, int* index) const
	{
		assert(0 <= i && i <= j && j < n_);

		int ret_max = -1;
		int index_begin = 0;
		int size = n_;
		while (1)
		{
			if (i & 1)
			{
				if (ret_max < data_[index_begin + i])
				{
					ret_max = data_[index_begin + i];
					*index = index_[index_begin + i];
				}
				++i;
			}
			if ((j & 1) == 0)
			{
				if (ret_max < data_[index_begin + j])
				{
					ret_max = data_[index_begin + j];
					*index = index_[index_begin + j];
				}
				--j;
			}
			if (i > j)
			{
				return ret_max;
			}
			index_begin += size;
			size /= 2;
			i /= 2;
			j /= 2;
		}
	}
};

class Graph
{
private:
	std::vector<int> edge_data_;
	std::vector<int*> edge_;
	std::vector<int> length_;

public:
	// V : num of vertices
	// E : num of edges
	// Edge[i] = {A[i], B[i]}
	Graph(int V, int E, const int A[], const int B[])
	{
		edge_data_ = std::vector<int>(E * 2);
		edge_ = std::vector<int*>(V);
		length_ = std::vector<int>(V);

		for (int i = 0; i < E; ++i)
		{
			++length_[A[i]];
			++length_[B[i]];
		}

		edge_[0] = edge_data_.data();
		for (int i = 0; i < V - 1; ++i)
		{
			edge_[i + 1] = edge_[i] + length_[i];
		}

		memset(length_.data(), 0, V * sizeof(int));

		for (int i = 0; i < E; ++i)
		{
			edge_[A[i]][length_[A[i]]++] = B[i];
			edge_[B[i]][length_[B[i]]++] = A[i];
		}
	}

	// returns num of Vertices
	inline int getV() const
	{
		return length_.size();
	}

	// returns num of Edges
	inline int getE() const
	{
		return edge_data_.size() >> 1;
	}

	inline int getLength(int nodeIndex) const
	{
		return length_[nodeIndex];
	}

	inline int getEdge(int nodeIndex, int index) const
	{
		return edge_[nodeIndex][index];
	}

	void print() const
	{
		for (int i = 0; i < getV(); ++i)
		{
			printf("%d : ", i);
			for (int j = 0; j < getLength(i); ++j)
			{
				printf("%d ", getEdge(i, j));
			}
			printf("\n");
		}
	}
};

class BiconnectGraph_
{
public:
	Graph* g_;
	std::vector<int>* index_;

	BiconnectGraph_(Graph* g)
	{
		Builder builder;
		*this = builder.DecomposeToBiconnectedComponents(g);
	}

protected:
	void close()
	{
		delete g_;
		delete index_;
	}

private:
	BiconnectGraph_(Graph* g, std::vector<int>* index)
		:g_(g),
		index_(index)
	{}

	class Builder
	{
	public:
		Graph* g;
		std::vector<int> ord;
		std::vector<int> low;
		std::vector<bool> visited;
		int k;

		std::vector<int> A;
		std::vector<int> B;
		std::vector<int>* newIndex;

		// 二重辺連結成分分解
		// use lowlink http://hos.ac/slides/20110504_graph.pdf
		BiconnectGraph_ DecomposeToBiconnectedComponents(Graph* g)
		{
			this->g = g;
			ord = std::vector<int>(g->getV());
			low = std::vector<int>(g->getV());
			visited = std::vector<bool>(g->getV());
			k = 0;

			A = std::vector<int>(g->getE());
			B = std::vector<int>(g->getE());
			newIndex = new std::vector<int>(g->getV());

			// update ord, low
			dfs_lowlink(0);

			// update k, A, B, newIndex
			visited.assign(g->getV(), false);
			k = 0;
			(*newIndex)[0] = 0;
			dfs_create_graph_info(0);

			//print();

			return BiconnectGraph_(
				new Graph(k + 1, k, A.data(), B.data()),
				newIndex);
		}

		// Lowlink
		// gain information (ord, low) for decomposition
		void dfs_lowlink(int u, int prev = -1)
		{
			visited[u] = true;
			low[u] = ord[u] = k;
			++k;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (!visited[v])
				{
					dfs_lowlink(v, u);
					low[u] = std::min(low[u], low[v]);
				}
				else if (v != prev)
				{
					low[u] = std::min(low[u], ord[v]);
				}
			}
		}

		// create new graph info
		// change k, A, B, newIndex
		void dfs_create_graph_info(int u)
		{
			visited[u] = true;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (!visited[v])
				{
					assert(ord[u] < ord[v]);
					if (ord[u] < low[v])
					{
						// (u, v) is a bridge
						A[k] = (*newIndex)[u];
						B[k] = (*newIndex)[v] = k + 1;
						k = k + 1;
					}
					else
					{
						(*newIndex)[v] = (*newIndex)[u];
					}
					dfs_create_graph_info(v);
				}
			}
		}

		void print() const
		{
			printf("| ord | low | visited | newIndex |\n");
			for (int i = 0; i < g->getV(); ++i)
			{
				printf("|%4d |%4d |     %3d | %8d |\n", ord[i],
				                                        low[i],
				                                        visited[i],
				                                        (*newIndex)[i]);
			}
		}
	};
};

class BiconnectGraph : private BiconnectGraph_
{
public:
	BiconnectGraph(Graph* g) : BiconnectGraph_(g) {}
	~BiconnectGraph()
	{
		close();
	}

	inline Graph& graph() const
	{
		return *g_;
	}

	inline std::vector<int>& index() const
	{
		return *index_;
	}

	void print() const
	{
		graph().print();

		printf("i: reindex\n");
		for (int i = 0; i < index().size(); ++i)
		{
			printf("%d : %d\n", i, index().at(i));
		}
	}
};


class HLDecompositionGraph
{
public:
	std::vector<int> index_to_groupid;
	std::vector<int> index_to_groupindex;
	std::vector<int> groupid_to_parent_groupid;
	std::vector<int> groupid_to_parent_groupindex;
	std::vector<int> groupid_to_size;
	int group_count;

	std::vector<std::vector<int>> add_count;

	HLDecompositionGraph(BiconnectGraph* biGraph,
	                     std::vector<int>* biconnect_add_count)
		: index_to_groupid(biGraph->index().size()),
		index_to_groupindex(biGraph->index().size()),
		groupid_to_parent_groupid(biGraph->graph().getV()),
		groupid_to_parent_groupindex(biGraph->graph().getV()),
		groupid_to_size(biGraph->graph().getV())
	{
		Builder builder;
		builder.HLDecompose(this, biGraph, biconnect_add_count);
	}

	void print() const
	{
		printf(" i:   gid gindex\n");
		for (int i = 0; i < index_to_groupid.size(); ++i)
		{
			printf("%2d: %5d %5d\n",
				i,
				index_to_groupid[i],
				index_to_groupindex[i]);
		}

		printf("gid:   p_gid p_gindex\n");
		for (int i = 0; i < groupid_to_parent_groupid.size(); ++i)
		{
			printf("%2d: %5d %5d\n",
				i,
				groupid_to_parent_groupid[i],
				groupid_to_parent_groupindex[i]);
		}
	}

	class Builder
	{
	public:
		HLDecompositionGraph* decomposision;
		Graph* g;
		BiconnectGraph* bg;
		std::vector<int>* baddcount;
		// last group id
		int k;
		std::vector<int> depth_;
		std::vector<int> pre_index_to_groupid;
		std::vector<int> pre_index_to_groupindex;
		
		void HLDecompose(HLDecompositionGraph* decomposition,
		                 BiconnectGraph* g,
		                 std::vector<int>* biconnect_add_count)
		{
			this->decomposision = decomposition;
			this->g = &g->graph();
			bg = g;
			baddcount = biconnect_add_count;
			k = 0;
			depth_ = std::vector<int>(g->graph().getV());
			pre_index_to_groupid = std::vector<int>(g->graph().getV());
			pre_index_to_groupindex = std::vector<int>(g->graph().getV());

			// find deepest node (doesnt make much of difference)
			// use this (submission 193255) => 256 ms
			// not use  (submission 193256) => 256 ms
			NodeInfo deepest_node = dfs_find_deepest(0);

			// update depth_
			dfs_depth(deepest_node.index);

			// HL decomposition
			dfs_hl_decomposition(deepest_node.index, 0, -1);

			// set group_count
			decomposision->group_count = k + 1;

			// reindex and set add_count
			decomposition->add_count
				= std::vector<std::vector<int>>(decomposision->group_count);
			for (int i = 0; i < decomposision->group_count; ++i)
			{
				decomposision->add_count[i]
					= std::vector<int>(decomposision->groupid_to_size[i]);
			}
			for (int i = 0; i < g->index().size(); ++i)
			{
				int bindex = g->index()[i];
				int groupid = pre_index_to_groupid[bindex];
				int groupindex = pre_index_to_groupindex[bindex];

				// reindex (pre_index to decomposition.index)
				decomposision->index_to_groupid[i] = groupid;
				decomposision->index_to_groupindex[i] = groupindex;

				// set add_count
				if ((groupindex & 1) == 0)
				{
					assert((*biconnect_add_count)[bindex]);
					decomposition->add_count[groupid][groupindex >> 1]
						= (*biconnect_add_count)[bindex];
				}
			}
		}

		struct NodeInfo
		{
			int depth;
			int index;
		};

		NodeInfo dfs_find_deepest(int u, int prev = -1)
		{
			NodeInfo info = {0, u};
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					NodeInfo leafInfo = dfs_find_deepest(v, u);
					if (leafInfo.depth > info.depth)
					{
						info = leafInfo;
					}
				}
			}
			++info.depth;
			return info;
		}

		// update depth_
		int dfs_depth(int u, int prev = -1)
		{
			int depth = 0;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					depth = std::max(depth, dfs_depth(v, u));
				}
			}
			depth_[u] = depth;
			return depth + 1;
		}

		void dfs_hl_decomposition(int u,
		                          int group_id,
		                          int empty_group_index,
		                          int prev = -1)
		{
			// calc group_index
			int group_index;
			int next_empty_group_index;
			if ((*baddcount)[u])
			{
				group_index = empty_group_index + 1;
				next_empty_group_index = empty_group_index + 2;

				// increment group_size
				++decomposision->groupid_to_size[group_id];
			}
			else
			{
				group_index = empty_group_index;
				next_empty_group_index = empty_group_index;
			}

			// set index
			pre_index_to_groupid[u] = group_id;
			pre_index_to_groupindex[u] = group_index;

			// identify deepest
			int max_depth = -1;
			int max_depth_index = -1;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					if (depth_[v] > max_depth)
					{
						max_depth = depth_[v];
						max_depth_index = v;
					}
				}
			}

			// devide into the Heavy and the Light
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					if (v == max_depth_index)
					{
						// Heavy
						dfs_hl_decomposition(v, group_id, next_empty_group_index, u);
					}
					else
					{
						// Light
						++k;
						decomposision->groupid_to_parent_groupid[k] = group_id;
						decomposision->groupid_to_parent_groupindex[k] = group_index;
						dfs_hl_decomposition(v, k, -1, u);
					}
				}
			}
		}
	};
};

class Solver
{
public:
	using QueType = std::priority_queue<int>;

	// How to compact index
	//
	// Consider that group_i has 7 elements but never updates 3 elements,
	// for instance [0 x x 1 2 x 3].
	// As indices in group_i,
	// I use doubled indices for variable elements
	// and odd indices for always empty elements.
	// So in case [0 x x 1 2 x 3],
	// I use      [0 1 1 2 4 5 6].
	// This reindex allows you to reduce memories but to handle range queries.
	// You can reindex the index [x, y] to the range-query index [(x + x&1)/2, y/2].
	HLDecompositionGraph* g;
	std::vector<std::vector<QueType>>* que_list;
	std::vector<SegTree>* seg_list;

	inline int toleft(int x)
	{
		if (x & 1)
		{
			return (x + 1) >> 1;
		}
		else
		{
			return x >> 1;
		}
	}

	inline int toright(int y)
	{
		return y >> 1;
	}

	// V : num of vertices
	// E : num of edges
	// Edge[i] = {A[i], B[i]}
	Solver(int V, int E, const int A[], const int B[], const int add_count[])
	{
		// build normal graph
		Graph original_graph(V, E, A, B);
		TimePrint("graph");

		// build biconnect graph
		BiconnectGraph biconnect_graph(&original_graph);
		TimePrint("bigraph");

		// count biconnect_add
		std::vector<int> biconnect_add_count(biconnect_graph.index().size());
		for (int i = 0; i < V; ++i)
		{
			int biconnect_index = biconnect_graph.index()[i];
			biconnect_add_count[biconnect_index] += add_count[i];
		}
		TimePrint("count biconnect_add");

		// build HL Decomposition graph
		g = new HLDecompositionGraph(&biconnect_graph, &biconnect_add_count);
		TimePrint("HLDgraph");

		//original_graph.print();
		//biconnect_graph.print();
		//g->print();

		// initialize que_list
		que_list = new std::vector<std::vector<QueType>>(g->group_count);
		for (int i = 0; i < g->group_count; ++i)
		{
			(*que_list)[i] = std::vector<QueType>();
			(*que_list)[i].reserve(g->groupid_to_size[i]);
		}

		// reserve que
		for (int i = 0; i < g->group_count; ++i)
		{
			for (int j = 0; j < g->groupid_to_size[i]; ++j)
			{
				std::vector<int> que_vec;
				que_vec.reserve(g->add_count[i][j]);
				(*que_list)[i].push_back(QueType(std::less<int>(),
					                        std::move(que_vec)));
			}
		}

		// initialize seq_list
		seg_list = new std::vector<SegTree>();
		seg_list->reserve(g->group_count);
		for (int i = 0; i < g->group_count; ++i)
		{
			seg_list->emplace_back(g->groupid_to_size[i]);
		}
	}

	void query1(int u, int w)
	{
		int group_id = g->index_to_groupid[u];
		int group_index = g->index_to_groupindex[u];
		assert((group_index & 1) == 0 && g->add_count[group_id][group_index >> 1]);
		int data_index = group_index >> 1;

		(*que_list)[group_id][data_index].push(w);

		auto& seg = (*seg_list)[group_id];
		if (w > seg.data_[data_index])
		{
			seg.update(data_index, w);
		}
	}

	int query2(int s, int t)
	{
		int group_id_0 = g->index_to_groupid[s];
		int group_index_0 = g->index_to_groupindex[s];
		int group_id_1 = g->index_to_groupid[t];
		int group_index_1 = g->index_to_groupindex[t];

		int max_value = -1;
		int group_id_max = -1;
		int group_data_index_max = -1;

		while (1)
		{
			if (group_id_0 == group_id_1)
			{
				if ((group_index_0 & 1)
					&& (group_index_0 == group_index_1))
				{
					break;
				}

				if (group_index_0 > group_index_1)
				{
					std::swap(group_index_0, group_index_1);
				}

				int data_index_0 = toleft(group_index_0);
				int data_index_1 = toright(group_index_1);
				assert(data_index_0 <= data_index_1);

				int index;
				int value = (*seg_list)[group_id_0]
				            .getmax(data_index_0, data_index_1, &index);
				if (value > max_value)
				{
					max_value = value;
					group_id_max = group_id_0;
					group_data_index_max = index;
				}
				break;
			}

			if (group_id_0 < group_id_1)
			{
				std::swap(group_id_0, group_id_1);
				std::swap(group_index_0, group_index_1);
			}
			assert(group_id_0 > group_id_1);
			{
				if (group_index_0 >= 0)
				{
					int data_index_0 = toright(group_index_0);

					int index;
					int value = (*seg_list)[group_id_0]
					            .getmax(data_index_0, &index);
					if (value > max_value)
					{
						max_value = value;
						group_id_max = group_id_0;
						group_data_index_max = index;
					}
				}
				group_index_0 = g->groupid_to_parent_groupindex[group_id_0];
				group_id_0 = g->groupid_to_parent_groupid[group_id_0];
			}
		}

		if (max_value > 0)
		{
			assert(group_id_max != -1);
			assert(group_data_index_max != -1);

			// update que
			auto& que = (*que_list)[group_id_max][group_data_index_max];
			assert(que.top() == max_value);
			que.pop();

			// get que value
			int value;
			if (que.empty())
			{
				value = -1;
			}
			else
			{
				value = que.top();
			}

			// update segtree
			(*seg_list)[group_id_max].update(group_data_index_max, value);
		}

		return max_value;
	}

	~Solver()
	{
		delete g;
		delete que_list;
		delete seg_list;
	}
};

char input_buf[(200000 * 2) * 16];
char output_buf[100000 * 16];

int N, M, Q;
int A[200000], B[200000];
int q[200000], a[200000], b[200000];

int add_count[100000] = {};

int main()
{
	TimePrint("start");

	// input
	fread(input_buf, sizeof(char), sizeof(input_buf), stdin);
	{
		char* p = input_buf;

		// N
		N = 0;
		while (*p != ' ')
			N = 10 * N + (int)(*p++ - '0');
		++p;

		// M
		M = 0;
		while (*p != ' ')
			M = 10 * M + (int)(*p++ - '0');
		++p;

		// Q
		Q = 0;
		while (*p != '\n')
			Q = 10 * Q + (int)(*p++ - '0');
		++p;

		// A, B
		for (int i = 0; i < M; ++i)
		{
			// A
			int A_ = 0;
			while (*p != ' ')
				A_ = 10 * A_ + (int)(*p++ - '0');
			++p;

			// B
			int B_ = 0;
			while (*p != '\n')
				B_ = 10 * B_ + (int)(*p++ - '0');
			++p;

			A[i] = A_ - 1;
			B[i] = B_ - 1;
		}

		// q, a, b
		for (int i = 0; i < Q; ++i)
		{
			// q
			int q_ = 0;
			q_ = (int)(*p++ - '1');
			++p;

			// a
			int a_ = 0;
			while (*p != ' ')
				a_ = 10 * a_ + (int)(*p++ - '0');
			++p;

			// b
			int b_ = 0;
			while (*p != '\n')
				b_ = 10 * b_ + (int)(*p++ - '0');
			++p;

			if (!q_) // query 1
			{
				q[i] = q_;
				a[i] = a_ - 1;
				b[i] = b_;

				++add_count[a_ - 1];
			}
			else // query 2
			{
				q[i] = q_;
				a[i] = a_ - 1;
				b[i] = b_ - 1;
			}
		}
	}
	TimePrint("input");

	// construct solver
	Solver solver(N, M, A, B, add_count);
	TimePrint("solver constructor");

	// query
	{
		char* p = output_buf;
		for (int i = 0; i < Q; ++i)
		{
			if (!q[i]) // query 1
			{
				solver.query1(a[i], b[i]);
			}
			else // query 2
			{
				int query_ret = solver.query2(a[i], b[i]);

				// int => string
				if (query_ret < 0)
				{
					*p++ = '-';
					*p++ = '1';
					*p++ = '\n';
				}
				else
				{
					char num_buf[16];
					int length = 0;
					while (query_ret)
					{
						num_buf[length] = query_ret % 10;
						query_ret /= 10;
						++length;
					}
					for (int j = 1; j <= length; ++j)
					{
						*p++ = num_buf[length - j] + '0';
					}
					*p++ = '\n';
				}
			}
		}
		fwrite(output_buf, sizeof(char), p - output_buf, stdout);
	}
	TimePrint("query");
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード