oj.uz

답안 #61838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61838 2018-07-26T20:28:47 Z kingpig9 도서관 (JOI18_library) C++11
0 / 100
 74 ms 1328 KB 
#include <bits/stdc++.h>
#include "library.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1010;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
vector<pii> edges;
int cache[MAXN][MAXN];

vector<int> getvec (int lt, int rt) {
	vector<int> v(N);
	for (int i = lt; i <= rt; i++) {
		v[i] = true;
	}
	return v;
}

int query (int lt, int rt) {
	if (cache[lt][rt]) {
		return cache[lt][rt];
	}

	//how many of them are in the range lt, rt?
	return cache[lt][rt] = (lt == rt ? 1 : Query(getvec(lt, rt)));
}

int pquery[MAXN];

int getnew (int lt, int rt) {
	//what happens when you add rt? how many components does it change by?
	return query(lt, rt) - query(lt, rt - 1);
}

vector<int> adj[MAXN];

void Solve (int nnn) {
	N = nnn;
	
	for (int rt = 1; rt < N; rt++) {
		//check if 
		int qdiff = getnew(0, rt);
		if (qdiff == +1) {
			//no edges added
		} else if (qdiff == 0) {
			//one edge added -- where is it?
			int lo = 0, hi = rt;	//lo for sure <= other endpt, hi for sure NOT true
			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				if (getnew(mid, rt) == 0) {
					lo = mid;
				} else {
					hi = mid;
				}
			}
			edges.push_back({lo, rt});
		} else if (qdiff == -1) {
			//TWO edges added!!!
			int lo = 0, hi = rt;
			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				if (getnew(mid, rt) < 1) {
					lo = mid;
				} else {
					hi = mid;
				}
			}
			edges.push_back({lo, rt});

			tie(lo, hi) = pii(0, lo);
			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				if (getnew(mid, rt) < 0) {
					lo = mid;
				} else {
					hi = mid;
				}
			}
			edges.push_back({lo, rt});
		} else {
			assert(!"Bad qdiff");
		}
	}

	for (pii e : edges) {
		adj[e.fi].push_back(e.se);
		adj[e.se].push_back(e.fi);
	}

	int leaf = 0;
	while (adj[leaf].size() != 1) {
		leaf++;
	}

	vector<int> ans;
	int cur = leaf, prv = 0;
	while (ans.size() < N) {
		ans.push_back(cur + 1);
		for (int i : adj[cur]) {
			if (i != prv) {
				tie(cur, prv) = pii(i, cur);
				break;
			}
		}
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.size() < N) {
         ~~~~~~~~~~~^~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 972 KB Output is correct
2 Correct 69 ms 1204 KB Output is correct
3 Correct 74 ms 1204 KB Output is correct
4 Correct 41 ms 1204 KB Output is correct
5 Correct 57 ms 1216 KB Output is correct
6 Correct 55 ms 1268 KB Output is correct
7 Correct 53 ms 1272 KB Output is correct
8 Correct 63 ms 1280 KB Output is correct
9 Correct 60 ms 1328 KB Output is correct
10 Correct 34 ms 1328 KB Output is correct
11 Incorrect 4 ms 1328 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 972 KB Output is correct
2 Correct 69 ms 1204 KB Output is correct
3 Correct 74 ms 1204 KB Output is correct
4 Correct 41 ms 1204 KB Output is correct
5 Correct 57 ms 1216 KB Output is correct
6 Correct 55 ms 1268 KB Output is correct
7 Correct 53 ms 1272 KB Output is correct
8 Correct 63 ms 1280 KB Output is correct
9 Correct 60 ms 1328 KB Output is correct
10 Correct 34 ms 1328 KB Output is correct
11 Incorrect 4 ms 1328 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -