oj.uz

Submission #769204

# Submission time Handle Problem Language Result Execution time Memory
769204 2023-06-29T09:51:41 Z marvinthang Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 2097152 KB 
/*************************************
*    author: marvinthang             *
*    created: 29.06.2023 15:49:29    *
*************************************/

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

int N;
vector <vector <bool>> visited;

int get_prev(int i, int j) {
	i -= j;
	return i < 0 ? i + N : i;
}

int get_next(int i, int j) {
	i += j;
	return i >= N ? i - N : i;
}

vector <int> st, lazy;

void build(int i, int l, int r, vector <int> &v) {
	if (r - l == 1) {
		st[i] = v[l];
		return;
	}
	int m = l + r >> 1;
	build(i << 1, l, m, v);
	build(i << 1 | 1, m, r, v);
	st[i] = min(st[i << 1], st[i << 1 | 1]);
}

void pushDown(int i) {
	if (!lazy[i]) return;
	st[i << 1] += lazy[i];
	lazy[i << 1] += lazy[i];
	st[i << 1 | 1] += lazy[i];
	lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0;
}

int find_zero(void) {
	int i = 1, l = 0, r = N;
	while (true) {
		if (r - l == 1) return l;
		pushDown(i);
		int m = l + r >> 1;
		if (!st[i << 1]) i = i << 1, r = m;
		else i = i << 1 | 1, l = m;
	}
	return -1;
}

void update(int i, int l, int r, int u, int v, int add) {
	if (l >= v || r <= u) return;
	if (u <= l && r <= v) {
		st[i] += add;
		lazy[i] += add;
		return;
	}
	pushDown(i);
	int m = l + r >> 1;
	update(i << 1, l, m, u, v, add);
	update(i << 1 | 1, m, r, u, v, add);
	st[i] = min(st[i << 1], st[i << 1 | 1]);
}

int dist(int i, int j) {
	return i < j ? j - i : j + N - i;
}

void init(int k, vector <int> r) {
	N = r.size();
	st.resize(N * 4 + 23);
	lazy.resize(N * 4 + 23);
	build(1, 0, N, r);
	vector <int> h(N);
	--k;
	vector <vector <int>> adj(N);
	set <int> pos_zero, good_zero;
	REPD(v, N) {
		while (!st[1]) {
			int p = find_zero();
			update(1, 0, N, p, p + 1, 1e9);
			auto it = pos_zero.insert(p).fi;
			if (pos_zero.size() == 1) {
				good_zero.insert(p);
				continue;
			}
			int prv = it == pos_zero.begin() ? *pos_zero.rbegin() : *prev(it);
			int nxt = next(it) == pos_zero.end() ? *pos_zero.begin() : *next(it);
			if (dist(prv, p) > k) good_zero.insert(p);
			if (dist(p, nxt) <= k) good_zero.erase(nxt);
		}
		int i = *good_zero.begin();
		good_zero.erase(good_zero.begin());
		auto it = pos_zero.find(i);
		int prv = it == pos_zero.begin() ? *pos_zero.rbegin() : *prev(it);
		int nxt = next(it) == pos_zero.end() ? *pos_zero.begin() : *next(it);
		pos_zero.erase(it);
		if (!pos_zero.empty() && dist(prv, nxt) > k) good_zero.insert(nxt);

		h[i] = v;
		prv = get_prev(i, k);
		if (prv < i) update(1, 0, N, prv, i, -1);
		else {
			update(1, 0, N, prv, N, -1);
			update(1, 0, N, 0, i, -1);
		}
	}
	set <pair <int, int>> left, right;
	REP(i, k) {
		int x = get_prev(0, i + 1);
		left.insert(make_pair(h[x], x));
		x = get_next(0, i + 1);
		right.insert(make_pair(h[x], x));
	}
	REP(i, N) {
		auto it = left.lower_bound(make_pair(h[i], i));
		if (it != left.begin()) adj[i].push_back(prev(it)->se);
		it = right.lower_bound(make_pair(h[i], i));
		if (it != right.begin()) adj[i].push_back(prev(it)->se);
		int x = get_prev(i, k);
		left.erase(make_pair(h[x], x));
		left.insert(make_pair(h[i], i));

		x = get_next(i, 1);
		right.erase(make_pair(h[x], x));
		x = get_next(i, k + 1);
		right.insert(make_pair(h[x], x));
	}

	visited.resize(N, vector<bool>(N));
	REP(i, N) {
		queue <int> q;
		q.push(i);
		visited[i][i] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v: adj[u]) if (!visited[i][v]) {
				visited[i][v] = 1;
				q.push(v);
			}
		}
	}
}

int compare_plants(int x, int y) {
	if (visited[x][y]) return 1;
	if (visited[y][x]) return -1;
	return 0;
}

Compilation message

plants.cpp: In function 'void build(int, int, int, std::vector<int>&)':
plants.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m = l + r >> 1;
      |          ~~^~~
plants.cpp: In function 'int find_zero()':
plants.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int m = l + r >> 1;
      |           ~~^~~
plants.cpp: In function 'void update(int, int, int, int, int, int)':
plants.cpp:101:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 42 ms 4044 KB Output is correct
7 Correct 93 ms 56456 KB Output is correct
8 Execution timed out 4151 ms 1913072 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 692 KB Output is correct
7 Correct 218 ms 9048 KB Output is correct
8 Correct 2 ms 388 KB Output is correct
9 Correct 7 ms 696 KB Output is correct
10 Correct 184 ms 8728 KB Output is correct
11 Correct 115 ms 8468 KB Output is correct
12 Correct 113 ms 8760 KB Output is correct
13 Correct 214 ms 8856 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 692 KB Output is correct
7 Correct 218 ms 9048 KB Output is correct
8 Correct 2 ms 388 KB Output is correct
9 Correct 7 ms 696 KB Output is correct
10 Correct 184 ms 8728 KB Output is correct
11 Correct 115 ms 8468 KB Output is correct
12 Correct 113 ms 8760 KB Output is correct
13 Correct 214 ms 8856 KB Output is correct
14 Execution timed out 4022 ms 57268 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 54 ms 4588 KB Output is correct
4 Runtime error 1833 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 9 ms 1212 KB Output is correct
8 Correct 10 ms 1292 KB Output is correct
9 Correct 10 ms 1236 KB Output is correct
10 Correct 10 ms 1284 KB Output is correct
11 Correct 9 ms 1236 KB Output is correct
12 Correct 10 ms 1236 KB Output is correct
13 Correct 10 ms 1236 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Runtime error 1049 ms 2097152 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 42 ms 4044 KB Output is correct
7 Correct 93 ms 56456 KB Output is correct
8 Execution timed out 4151 ms 1913072 KB Time limit exceeded
9 Halted 0 ms 0 KB -