Submission #67605

#	Time	Username	Problem	Language	Result	Execution time	Memory
67605		Mamnoon_Siam	Library (JOI18_library)	C++17	100 / 100	828 ms	964 KiB

library

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include "library.h"
// #include <bits/extc++.h>
using namespace std;

#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a, val) memset(a, val, sizeof (a))
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}

template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
	return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;

template<typename T> using min_pq =
	std::priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const int maxn = 1005;
 
int n;
vector<int> g[maxn];
int vis[maxn];

void dfs(int u, int l, int r) {
	vis[u] = 1;
	for(int v : g[u]) {
		if(!vis[v] and l <= v and v <= r) {
			dfs(v, l, r);
		}
	}
}

bool HasExtraEdges(int l, int r) {
	int cc = 0;
	memset(vis, 0, sizeof vis);
	for(int i = l; i <= r; i++) {
		if(!vis[i]) {
			cc++;
			dfs(i, l, r);
		}
	}
	vector<int> tmp(n);
	for(int i = l; i <= r; i++) {
		tmp[i] = 1;
	}
	return Query(tmp) < cc;
}
 
void Solve(int N) {
	n = N;
	int rnd = n-1;
	while(rnd--) {
		int L = -1, R = -1, lo, hi, mid;

		lo = 0, hi = n - 1;
		while(lo <= hi) {
			int mid = lo + hi >> 1;
			if(HasExtraEdges(0, mid)) {
				R = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}

		lo = 0, hi = R - 1;
		while(lo <= hi) {
			int mid = lo + hi >> 1;
			if(HasExtraEdges(mid, R)) {
				L = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
		assert(L != -1 and R != -1);

		g[L].emplace_back(R);
		g[R].emplace_back(L);
	}

	vector<int> ans;
	function<void(int)> fill = [&](int u) {
		vis[u] = 1;
		ans.emplace_back(u + 1);
		for(int v : g[u]) {
			if(!vis[v]) {
				fill(v);
			}
		}
	};

	memset(vis, 0, sizeof vis);
	for(int i = 0; i < n; i++) {
		if(g[i].size() <= 1) {
			fill(i);
			break;
		}
	}
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'int myrand(int, int)':
library.cpp:19:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
library.cpp:19:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
library.cpp: In function 'void Solve(int)':
library.cpp:74:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
library.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
library.cpp:70:31: warning: unused variable 'mid' [-Wunused-variable]
   int L = -1, R = -1, lo, hi, mid;
                               ^~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81