Submission #45038

#	Time	Username	Problem	Language	Result	Execution time	Memory
45038		RayaBurong25_1	Library (JOI18_library)	C++17	100 / 100	280 ms	848 KiB

library

#include <cstdio>
#include <vector>
#include <algorithm>
#include "library.h"
typedef struct cc cc;
struct cc
{
	std::vector<int> v;
};
std::vector<cc> All;
std::vector<int> M;
int test(int N, int s, int e, int exclude, int i)
{
	int j, k;
	for (j = 0; j < N; j++)
		M[j] = 0;
	for (j = s; j <= e; j++)
	{
		if (j == exclude) continue;
		for (k = 0; k < All[j].v.size(); k++)
			M[All[j].v[k]] = 1;
	}
	if (exclude < s || exclude > e)
		exclude = -1;
	// int cnt = Query(M);
	// printf("cnt %d should be %d\n", cnt, (e - s + 1) - (exclude != -1));
	M[i] = 1;
	int cnt = Query(M);
	// printf("s %d e %d cnt %d\n", s, e, cnt);
	if (cnt <= (e - s + 1) - (exclude != -1))
		return 1;
	else
		return 0;
}
int checkend(int N, int p, int i)
{
	int j, k;
	for (j = 0; j < N; j++)
		M[j] = 0;
	M[All[p].v.back()] = 1;
	M[i] = 1;
	int cnt = Query(M);
	if (cnt == 1)
		return 1;
	else
		return 0;
}
void Solve(int N)
{
	int CCo = 0, CCn;
	int i, j, k;
	for (i = 0; i < N; i++)
		M.push_back(0);
	cc nothing;
	int mn, md, mx, t;
	for (i = 0; i < N; i++)
	{
		// printf("i%d\n", i);
		for (j = 0; j <= i; j++)
			M[j] = 1;
		for (j = i + 1; j < N; j++)
			M[j] = 0;
		// M[i] = 1;
		CCn = Query(M);
		// printf("CCn %d\n", CCn);
		if (CCn > CCo)
		{
			All.push_back(nothing);
			All.back().v.push_back(i);
		}
		else if (CCn == CCo)
		{
			mn = 0;
			mx = All.size() - 1;
			while (mn != mx)
			{
				md = (mn + mx)/2;
				if (test(N, mn, md, -1, i))
				{
					mx = md;
				}
				else
				{
					mn = md + 1;
				}
			}
			if (All[mn].v.size() == 1)
				All[mn].v.push_back(i);
			else
			{
				if (!checkend(N, mn, i))
					std::reverse(All[mn].v.begin(), All[mn].v.end());
				All[mn].v.push_back(i);
			}
		}
		else
		{
			mn = 0;
			mx = All.size() - 1;
			while (mn != mx)
			{
				md = (mn + mx)/2;
				if (test(N, mn, md, -1, i))
				{
					mx = md;
				}
				else
				{
					mn = md + 1;
				}
			}
			if (All[mn].v.size() == 1)
				All[mn].v.push_back(i);
			else
			{
				if (!checkend(N, mn, i))
					std::reverse(All[mn].v.begin(), All[mn].v.end());
				All[mn].v.push_back(i);
			}
			t = mn;
			// printf("t %d\n", t);

			mn = 0;
			mx = All.size() - 1;
			while (mn != mx)
			{
				md = (mn + mx)/2;
				if (test(N, mn, md, t, i))
				{
					mx = md;
				}
				else
				{
					mn = md + 1;
				}
			}
			if (All[mn].v.size() == 1)
			{
				for (j = 0; j < All[mn].v.size(); j++)
					All[t].v.push_back(All[mn].v[j]);
				// printf("ok?\n");
				All[mn].v.clear();
				All.erase(All.begin() + mn);
				// printf("ok?\n");
			}
			else
			{
				if (checkend(N, mn, i))
					std::reverse(All[mn].v.begin(), All[mn].v.end());
				for (j = 0; j < All[mn].v.size(); j++)
					All[t].v.push_back(All[mn].v[j]);
				// printf("ok?\n");
				All[mn].v.clear();
				All.erase(All.begin() + mn);
				// printf("ok?\n");
			}
		}
		// printf("CC %d\n", CCn);
		CCo = CCn;
		// printf("All.size() %d\n", All.size());
		// for (j = 0; j < All.size(); j++)
		// {
		// 	printf("j%d : ", j);
		// 	for (k = 0; k < All[j].v.size(); k++)
		// 		printf("%d ", All[j].v[k]);
		// 	printf("\n");
		// }
	}

	std::vector<int> res(N);
	for (i = 0; i < N; i++)
	{
		res[i] = All[0].v[i] + 1;
	}
	Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'int test(int, int, int, int, int)':
library.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (k = 0; k < All[j].v.size(); k++)
               ~~^~~~~~~~~~~~~~~~~
library.cpp: In function 'int checkend(int, int, int)':
library.cpp:37:9: warning: unused variable 'k' [-Wunused-variable]
  int j, k;
         ^
library.cpp: In function 'void Solve(int)':
library.cpp:139:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < All[mn].v.size(); j++)
                 ~~^~~~~~~~~~~~~~~~~~
library.cpp:150:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < All[mn].v.size(); j++)
                 ~~^~~~~~~~~~~~~~~~~~
library.cpp:51:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81