oj.uz

Submission #67605

# Submission time Handle Problem Language Result Execution time Memory
67605 2018-08-15T05:49:22 Z Mamnoon_Siam Library (JOI18_library) C++17
100 / 100
 828 ms 964 KB 
//#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 332 KB Output is correct
2 Correct 57 ms 332 KB Output is correct
3 Correct 68 ms 344 KB Output is correct
4 Correct 87 ms 436 KB Output is correct
5 Correct 43 ms 552 KB Output is correct
6 Correct 65 ms 752 KB Output is correct
7 Correct 52 ms 752 KB Output is correct
8 Correct 59 ms 752 KB Output is correct
9 Correct 74 ms 752 KB Output is correct
10 Correct 39 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 2 ms 752 KB Output is correct
13 Correct 2 ms 752 KB Output is correct
14 Correct 4 ms 752 KB Output is correct
15 Correct 3 ms 752 KB Output is correct
16 Correct 7 ms 752 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 332 KB Output is correct
2 Correct 57 ms 332 KB Output is correct
3 Correct 68 ms 344 KB Output is correct
4 Correct 87 ms 436 KB Output is correct
5 Correct 43 ms 552 KB Output is correct
6 Correct 65 ms 752 KB Output is correct
7 Correct 52 ms 752 KB Output is correct
8 Correct 59 ms 752 KB Output is correct
9 Correct 74 ms 752 KB Output is correct
10 Correct 39 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 2 ms 752 KB Output is correct
13 Correct 2 ms 752 KB Output is correct
14 Correct 4 ms 752 KB Output is correct
15 Correct 3 ms 752 KB Output is correct
16 Correct 7 ms 752 KB Output is correct
17 Correct 735 ms 852 KB Output is correct
18 Correct 708 ms 852 KB Output is correct
19 Correct 814 ms 852 KB Output is correct
20 Correct 761 ms 852 KB Output is correct
21 Correct 645 ms 852 KB Output is correct
22 Correct 759 ms 852 KB Output is correct
23 Correct 828 ms 852 KB Output is correct
24 Correct 274 ms 852 KB Output is correct
25 Correct 792 ms 852 KB Output is correct
26 Correct 685 ms 852 KB Output is correct
27 Correct 268 ms 852 KB Output is correct
28 Correct 777 ms 964 KB Output is correct
29 Correct 764 ms 964 KB Output is correct
30 Correct 587 ms 964 KB Output is correct