답안 #45032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45032 2018-04-11T04:26:20 Z RayaBurong25_1 도서관 (JOI18_library) C++17
0 / 100
1585 ms 262144 KB
#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;
	}
	M[i] = 1;
	int cnt = Query(M);
	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);
		M[i] = 1;
		CCn = Query(M);
		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.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.erase(All.begin() + mn);
				// printf("ok?\n");
			}
		}
		// printf("CC %d\n", CCn);
		CCo = CCn;
		// for (j = 0; j < All.size(); 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

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:32:9: warning: unused variable 'k' [-Wunused-variable]
  int j, k;
         ^
library.cpp: In function 'void Solve(int)':
library.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < All[mn].v.size(); j++)
                 ~~^~~~~~~~~~~~~~~~~~
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:46:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1585 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1585 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -