답안 #58205 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58205	2018-07-17T07:01:28 Z	윤교준(#1690)	도서관 (JOI18_library)	C++11	100 / 100	689 ms	888 KB

library

#include "library.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define befv(V) ((V)[sz(V)-2])
using namespace std;

static const bool debug = 0;
static vector<int> G[1005];
static vector<int> AnsV;

static bitset<1005> chk;

static int N;

int Query(vector<int> &V, int n) {
	int SZ = sz(V) + !!n;
	if(!SZ) return 0;
	if(1 == SZ) return 1;

	vector<int> T(N, 0);
	for(int v : V) T[v-1] = 1;
	if(n) T[n-1] = 1;

	return Query(T);
}

void f(int idx, vector<int> &V) {
	if(V.empty()) return;
	if(1 == sz(V)) {
		G[idx].pb(V[0]);
		return;
	}

	if(debug) {
		printf("F idx=%d : ", idx);
		for(int v : V) printf("%d ", v);
		puts("");
	}

	int n = sz(V), m = n/2;
	
	vector<int> LV, RV;
	for(int i = 0; i < m; i++) LV.pb(V[i]);
	for(int i = m; i < n; i++) RV.pb(V[i]);

	int lvt = Query(LV, idx) - Query(LV, 0);
	if(-1 == lvt) {
		f(idx, LV);
		return;
	}
	if(!lvt) {
		f(idx, LV);
	}

	int rvt = Query(RV, idx) - Query(RV, 0);
	if(rvt < 1) {
		f(idx, RV);
	}
}

void g(int idx, int cnt, vector<int> &V) {
	if(!cnt || V.empty()) return;
	if(1 == sz(V)) {
		if(1 == Query(V, idx)) G[idx].pb(V[0]);
		return;
	}
	if(cnt == sz(V)) {
		for(int i = 0; i < cnt; i++)
			G[idx].pb(V[i]);
		return;
	}

	int n = sz(V), m = n/2;

	vector<int> LV, RV;
	for(int i = 0; i < m; i++) LV.pb(V[i]);
	for(int i = m; i < n; i++) RV.pb(V[i]);

	if(2 == cnt) {
		int lvt = Query(LV, idx) - Query(LV, 0);
		if(-1 == lvt) {
			g(idx, 2, LV);
			return;
		} else if(!lvt) {
			g(idx, 1, LV);
			g(idx, 1, RV);
			return;
		} else {
			g(idx, 2, RV);
			return;
		}
		return;
	}

	int lvt = Query(LV, idx) - Query(LV, 0);
	if(lvt) {
		g(idx, 1, RV);
	} else {
		g(idx, 1, LV);
	}
}

void Solve(int N) {
	::N = N;

	if(1 == N) {
		Answer(vector<int>{1});
		return;
	} else if(2 == N) {
		Answer(vector<int>{1, 2});
		return;
	}

	if(N <= 300) {
		for(int i = 1; i <= N; i++) {
			vector<int> V;
			for(int j = 1; j <= N; j++) if(j != i) V.pb(j);
			f(i, V);
		}
	} else {
		srand(20010610);
		int si = rand()%N + 1;

		if(debug) {
			printf("si=%d\n", si);
		}

		{
			vector<int> V;
			for(int j = 1; j <= N; j++) if(j != si) V.pb(j);
			g(si, 2, V);
		}

		vector<int> LV, RV;

		LV.pb(si); LV.pb(G[si][0]);
		RV.pb(si); RV.pb(G[si][1]);

		G[G[si][0]].pb(si);
		G[G[si][1]].pb(si);

		chk[si] = chk[G[si][0]] = chk[G[si][1]] = true;

		for(int i;;) {
			i = LV.back();
			if(debug) printf("LV %d\n", i);

			vector<int> V;
			for(int j = 1; j <= N; j++) if(!chk[j]) V.pb(j);

			g(i, 1, V);

			if(1 == sz(G[i])) break;

			int ni = G[i][0] + G[i][1] - befv(LV);
			G[ni].pb(i);
			chk[ni] = true;
			LV.pb(ni);

			i = ni;
		}

		for(int i;;) {
			i = RV.back();

			vector<int> V;
			for(int j = 1; j <= N; j++) if(!chk[j]) V.pb(j);

			g(i, 1, V);

			if(1 == sz(G[i])) break;

			int ni = G[i][0] + G[i][1] - befv(RV);
			G[ni].pb(i);
			chk[ni] = true;
			RV.pb(ni);

			i = ni;
		}
	}

	for(int i = 1; i <= N; i++) {
		sorv(G[i]);
		univ(G[i]);
	}

	if(debug) {
		for(int i = 1; i <= N; i++) {
			printf("%d G : ", i);
			for(int v : G[i]) printf("%d ", v);
			puts("");
		}
	}

	{
		int i = 1, pv;
		for(; 1 != sz(G[i]); i++);

		AnsV.pb(i); AnsV.pb(G[i][0]); pv = i;
		for(i = G[i][0]; 1 != sz(G[i]);) {
			AnsV.pb(G[i][0] + G[i][1] - pv);
			pv = i; i = AnsV.back();
		}
	}

	if(debug) {
		for(int v : AnsV) printf("%d ", v);
		puts("");
	}

	Answer(AnsV);
}

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	186 ms	456 KB	Output is correct
2	Correct	144 ms	456 KB	Output is correct
3	Correct	172 ms	516 KB	Output is correct
4	Correct	175 ms	548 KB	Output is correct
5	Correct	229 ms	648 KB	Output is correct
6	Correct	117 ms	648 KB	Output is correct
7	Correct	215 ms	648 KB	Output is correct
8	Correct	154 ms	648 KB	Output is correct
9	Correct	155 ms	648 KB	Output is correct
10	Correct	112 ms	700 KB	Output is correct
11	Correct	2 ms	700 KB	Output is correct
12	Correct	1 ms	700 KB	Output is correct
13	Correct	2 ms	700 KB	Output is correct
14	Correct	3 ms	700 KB	Output is correct
15	Correct	10 ms	700 KB	Output is correct
16	Correct	20 ms	700 KB	Output is correct

Subtask #2
81.0 / 81.0

#	결과	실행 시간	메모리	Grader output
1	Correct	186 ms	456 KB	Output is correct
2	Correct	144 ms	456 KB	Output is correct
3	Correct	172 ms	516 KB	Output is correct
4	Correct	175 ms	548 KB	Output is correct
5	Correct	229 ms	648 KB	Output is correct
6	Correct	117 ms	648 KB	Output is correct
7	Correct	215 ms	648 KB	Output is correct
8	Correct	154 ms	648 KB	Output is correct
9	Correct	155 ms	648 KB	Output is correct
10	Correct	112 ms	700 KB	Output is correct
11	Correct	2 ms	700 KB	Output is correct
12	Correct	1 ms	700 KB	Output is correct
13	Correct	2 ms	700 KB	Output is correct
14	Correct	3 ms	700 KB	Output is correct
15	Correct	10 ms	700 KB	Output is correct
16	Correct	20 ms	700 KB	Output is correct
17	Correct	512 ms	848 KB	Output is correct
18	Correct	445 ms	848 KB	Output is correct
19	Correct	640 ms	848 KB	Output is correct
20	Correct	465 ms	848 KB	Output is correct
21	Correct	638 ms	848 KB	Output is correct
22	Correct	573 ms	848 KB	Output is correct
23	Correct	689 ms	888 KB	Output is correct
24	Correct	179 ms	888 KB	Output is correct
25	Correct	647 ms	888 KB	Output is correct
26	Correct	514 ms	888 KB	Output is correct
27	Correct	204 ms	888 KB	Output is correct
28	Correct	555 ms	888 KB	Output is correct
29	Correct	504 ms	888 KB	Output is correct
30	Correct	577 ms	888 KB	Output is correct

답안 #58205

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 81.0 / 81.0

Subtask #1
19.0 / 19.0

Subtask #2
81.0 / 81.0