Submission #58201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58201	2018-07-17T06:44:38 Z	윤교준(#1690)	Library (JOI18_library)	C++11	19 / 100	2000 ms	996 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())
using namespace std;

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

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 Solve(int N) {
	::N = N;

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

	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);
	}

	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

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	248 KB	Output is correct
2	Correct	175 ms	436 KB	Output is correct
3	Correct	193 ms	444 KB	Output is correct
4	Correct	198 ms	552 KB	Output is correct
5	Correct	187 ms	624 KB	Output is correct
6	Correct	163 ms	624 KB	Output is correct
7	Correct	187 ms	624 KB	Output is correct
8	Correct	148 ms	628 KB	Output is correct
9	Correct	172 ms	628 KB	Output is correct
10	Correct	69 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	2 ms	712 KB	Output is correct
13	Correct	2 ms	712 KB	Output is correct
14	Correct	2 ms	712 KB	Output is correct
15	Correct	6 ms	712 KB	Output is correct
16	Correct	15 ms	712 KB	Output is correct

Subtask #2

0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	248 KB	Output is correct
2	Correct	175 ms	436 KB	Output is correct
3	Correct	193 ms	444 KB	Output is correct
4	Correct	198 ms	552 KB	Output is correct
5	Correct	187 ms	624 KB	Output is correct
6	Correct	163 ms	624 KB	Output is correct
7	Correct	187 ms	624 KB	Output is correct
8	Correct	148 ms	628 KB	Output is correct
9	Correct	172 ms	628 KB	Output is correct
10	Correct	69 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	2 ms	712 KB	Output is correct
13	Correct	2 ms	712 KB	Output is correct
14	Correct	2 ms	712 KB	Output is correct
15	Correct	6 ms	712 KB	Output is correct
16	Correct	15 ms	712 KB	Output is correct
17	Execution timed out	2023 ms	996 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-