oj.uz

Submission #61841

# Submission time Handle Problem Language Result Execution time Memory
61841 2018-07-26T20:37:57 Z kingpig9 Library (JOI18_library) C++11
100 / 100
 700 ms 4684 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;
	if (N == 1) {
		//SPECIAL CASE!!!
		Answer(vector<int> {1});
		return;
	} else if (N == 2) {
		Answer(vector<int> {1, 2});
		return;
	}
	
	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 = -1;
	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:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.size() < N) {
         ~~~~~~~~~~~^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 972 KB Output is correct
2 Correct 50 ms 1080 KB Output is correct
3 Correct 51 ms 1080 KB Output is correct
4 Correct 57 ms 1080 KB Output is correct
5 Correct 59 ms 1184 KB Output is correct
6 Correct 55 ms 1184 KB Output is correct
7 Correct 87 ms 1184 KB Output is correct
8 Correct 66 ms 1184 KB Output is correct
9 Correct 58 ms 1236 KB Output is correct
10 Correct 46 ms 1236 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 3 ms 1236 KB Output is correct
16 Correct 8 ms 1236 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 972 KB Output is correct
2 Correct 50 ms 1080 KB Output is correct
3 Correct 51 ms 1080 KB Output is correct
4 Correct 57 ms 1080 KB Output is correct
5 Correct 59 ms 1184 KB Output is correct
6 Correct 55 ms 1184 KB Output is correct
7 Correct 87 ms 1184 KB Output is correct
8 Correct 66 ms 1184 KB Output is correct
9 Correct 58 ms 1236 KB Output is correct
10 Correct 46 ms 1236 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 3 ms 1236 KB Output is correct
16 Correct 8 ms 1236 KB Output is correct
17 Correct 647 ms 4408 KB Output is correct
18 Correct 695 ms 4408 KB Output is correct
19 Correct 565 ms 4540 KB Output is correct
20 Correct 648 ms 4540 KB Output is correct
21 Correct 646 ms 4540 KB Output is correct
22 Correct 700 ms 4540 KB Output is correct
23 Correct 654 ms 4540 KB Output is correct
24 Correct 246 ms 4540 KB Output is correct
25 Correct 625 ms 4540 KB Output is correct
26 Correct 581 ms 4540 KB Output is correct
27 Correct 169 ms 4540 KB Output is correct
28 Correct 441 ms 4676 KB Output is correct
29 Correct 512 ms 4684 KB Output is correct
30 Correct 459 ms 4684 KB Output is correct