답안 #58201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58201 2018-07-17T06:44:38 Z 윤교준(#1690) 도서관 (JOI18_library) C++11
19 / 100
2000 ms 996 KB
#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);
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -