Submission #61841

#	Time	Username	Problem	Language	Result	Execution time	Memory
61841		kingpig9	Library (JOI18_library)	C++11	100 / 100	700 ms	4684 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81