oj.uz

Submission #825265

# Submission time Handle Problem Language Result Execution time Memory
825265 2023-08-14T16:30:24 Z thimote75 Comparing Plants (IOI20_plants) C++14
30 / 100
 1673 ms 116532 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
using iset  = set<int>;
using di    = pair<int, int>;

template<typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<typename T>
string to_string (T x) {
	string S = "[";
	bool first = true;
	for (const auto v : x) {
		if (!first)  S += ", ";
		S += to_string(v);
		first = false;
	}
	S += "]";
	return S;
}
string to_string( string s) {
	return s;
}
string to_string(bool b) {
	return to_string((int) b);
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
	cout << to_string(H) << " ";
	dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
#  define dbg(...)
#endif

void shift (idata &r, int count) {
	idata h;
	for (int i = count; i < r.size(); i ++)
		h.push_back(r[i]);
	for (int i = 0; i < count; i ++)
		h.push_back(r[i]);
	
	r.swap(h);
}

idata A;

int K, N;

struct SGData {
	int min_value = 1e9;
	int first_sol = 1e9;
	int first_min = 0;
	int  last_min = 0;
	int delta     = 0;

	void merge (SGData &left, SGData &right) {
		min_value = min(left.min_value, right.min_value);

		if (left.min_value == min_value)
			first_min = left.first_min;
		else first_min = right.first_min;

		if (right.min_value == min_value)
			last_min = right.last_min;
		else last_min = left.last_min;

		first_sol = 1e9;
		if ( left.min_value == min_value) first_sol = min(first_sol,  left.first_sol);
		if (right.min_value == min_value) first_sol = min(first_sol, right.first_sol);

		if (left.min_value == min_value
		&& right.min_value == min_value
		&& right.first_min - left.last_min >= K)
			first_sol = min(first_sol, right.first_min);

		min_value += delta;
	}
	void add (int dv) {
		min_value += dv;
		delta     += dv;
	}
	int answer (int N) {
		int e0 = last_min - N;
		int dt = first_min - e0;

		if (dt >= K) return first_min;
		return first_sol;
	}
};
string to_string (SGData data) {
	return "D[[" + to_string(data.first_min) + "; " + to_string(data.last_min) + "], " + to_string(data.min_value) + " " + to_string(data.first_sol) + " " + to_string(data.delta) + "]";
}
struct SegTree {
	vector<SGData> tree;

	int size, start, height;
	SegTree (int _size) {
		size   = _size;
		height = ceil(log2(size));
		start  = 1 << height;

		tree.resize(start << 1);

		for (int i = 0; i < size; i ++) {
			tree[i + start].min_value = 0;
			tree[i + start].first_min = i;
			tree[i + start]. last_min = i;
		}

		for (int i = start - 1; i >= 1; i --)
			tree[i].merge(tree[i * 2], tree[i * 2 + 1]);
	}

	void modify (int i, int value) {
		tree[i].add(value);

		while (i != 1) {
			i >>= 1;

			tree[i].merge(tree[i * 2], tree[i * 2 + 1]);
		}
	}
	void modify (int l, int r, int value) {
		l += start;
		r += start;

		while (l < r) {
			if ((l & 1) == 1) modify(l, value);
			if ((r & 1) == 0) modify(r, value);

			l = (l + 1) >> 1;
			r = (r - 1) >> 1;
		}

		if (l == r) modify(l, value);
	}
	void cmod (int l, int r, int v) {
		if (r < 0) {
			l += size;
			r += size;
		}

		if (l < 0) {
			modify(0, r, v);
			modify(l + size, size - 1, v);
		} else modify(l, r, v);
	}
	int query () {
		return tree[1].answer(size);
	}
};

template<typename T>
struct SegTreeMax {
	vector<T> tree;

	int start, size, height;
	SegTreeMax (int _size, T def) {
		size   = _size;
		height = ceil(log2(size));
		start  = 1 << height;

		tree.resize(start << 1, def);
	}

	void update (int index, T value) {
		index += start;
		tree[index] = value;

		while (index != 1) {
			index >>= 1;

			tree[index] = max(tree[index * 2], tree[index * 2 + 1]);
		}
	}
	T query (int l, int r, T def) {
		dbg(l, r, def);
		l += start;
		r += start;

		while (l < r) {
			if ((l & 1) == 1) def = max(def, tree[l]);
			if ((r & 1) == 0) def = max(def, tree[r]);
		
			l = (l + 1) >> 1;
			r = (r - 1) >> 1;
		}

		if (l == r) def = max(def, tree[l]);
		return def;
	}
	T cquery (int l, int r, T def) {
		if (l < 0)
			return max(query(0, r, def), query(l + size, size - 1, def));
		if (r >= size)
			return max(query(0, r - size, def), query(l, size - 1, def));
		return query(l, r, def);
	}
};

idata lw, rw;
igrid lw2k, rw2k;
igrid ld2k, rd2k;
const int MAXK = 20;

int distance (int a, int b) {
	if (a > b) swap(a, b);

	if (a == -1) return 1e9;

	return min(b - a, N + a - b);
}
void blfi (igrid &g, igrid &d, idata &v) {
	g.resize(v.size(), idata(MAXK, -1));
	d.resize(v.size(), idata(MAXK, 1e9));
	for (int i = 0; i < v.size(); i ++) {
		g[i][0] = v[i];
		d[i][0] = distance(v[i], i);
	}
	
	for (int k = 0; k + 1 < MAXK; k ++) {
		for (int i = 0; i < v.size(); i ++) {
			if (g[i][k] == -1) continue ;

			g[i][k + 1] = g[g[i][k]][k];
			d[i][k + 1] = d[i][k] + d[g[i][k]][k];
		}
	}
}

void init(int k, idata r) {
	K = k;
 
	idata r0 = r;
	int n = r.size(); N = n;
 
	A.resize(n);
 
	int s = 0;
 
	SegTree tree(n);
	for (int i = 0; i < n; i ++) tree.modify(i, i, r[i]);
	dbg(tree.tree);
 
	for (int v = n - 1; v >= 0; v --) {
		int p = tree.query();
 
		dbg(p);
 
		tree.modify(p, p, 1e9);
		
		int l = p - k + 1;
		int r = p - 1;
 
		tree.cmod(l, r, -1);
	
		A[p] = v;
		dbg(tree.tree);
	}

	idata AA(N);
	for (int i = 0; i < N; i ++)
		AA[A[i]] = i;

	lw.resize(N, -1);
	rw.resize(N, -1);

	di def = { -1e9, -1 };
	SegTreeMax<di> maxTree(N, def);
 
	for (int i = 0; i < N; i ++) {
		int j = AA[i];
		lw[j] = maxTree.cquery( j - K + 1, j - 1, def ).second;
		rw[j] = maxTree.cquery( j + 1, j - 1 + K, def ).second;

		maxTree.update( j, { i, j } );
	}

	blfi (lw2k, ld2k, lw);
	blfi (rw2k, rd2k, rw);

	return;
}

bool dfs (igrid &V, igrid &D, int s, int t, int dist_max) {
	int ct = 0;

	for (int k = MAXK - 1; k >= 0; k --) {
		if (ct + D[s][k] > dist_max || V[s][k] == -1) continue ;
		dbg(s, t, k, ct, dist_max, V[s][k], D[s][k]);

		ct += D[s][k];
		s   = V[s][k];
	}

	return distance(s, t) < K && A[s] >= A[t];
}
bool dfs (int s, int t) {
	return dfs(lw2k, ld2k, s, t, t > s ? N - t + s : s - t)
	    || dfs(rw2k, rd2k, s, t, t < s ? N - s + t : t - s);
}
 
int compare_plants(int x, int y) {
	bool hx = dfs(x, y);
	bool hy = dfs(y, x);
	if (hx == hy) return 0;

	if (hx) return 1;
	return -1;
}

Compilation message

plants.cpp: In function 'void shift(idata&, int)':
plants.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = count; i < r.size(); i ++)
      |                      ~~^~~~~~~~~~
plants.cpp: In function 'void blfi(igrid&, igrid&, idata&)':
plants.cpp:228:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |  for (int i = 0; i < v.size(); i ++) {
      |                  ~~^~~~~~~~~~
plants.cpp:234:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |   for (int i = 0; i < v.size(); i ++) {
      |                   ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, idata)':
plants.cpp:251:6: warning: unused variable 's' [-Wunused-variable]
  251 |  int s = 0;
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 57 ms 3032 KB Output is correct
7 Correct 143 ms 14392 KB Output is correct
8 Correct 541 ms 116340 KB Output is correct
9 Correct 571 ms 116400 KB Output is correct
10 Correct 677 ms 116444 KB Output is correct
11 Correct 705 ms 116408 KB Output is correct
12 Correct 738 ms 116532 KB Output is correct
13 Correct 864 ms 116448 KB Output is correct
14 Correct 829 ms 116388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 252 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 92 ms 5508 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 88 ms 5556 KB Output is correct
11 Correct 111 ms 5488 KB Output is correct
12 Correct 126 ms 5632 KB Output is correct
13 Correct 90 ms 5584 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 252 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 92 ms 5508 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 88 ms 5556 KB Output is correct
11 Correct 111 ms 5488 KB Output is correct
12 Correct 126 ms 5632 KB Output is correct
13 Correct 90 ms 5584 KB Output is correct
14 Correct 148 ms 14284 KB Output is correct
15 Incorrect 1673 ms 116452 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 113 ms 4128 KB Output is correct
4 Correct 1129 ms 116336 KB Output is correct
5 Correct 1116 ms 116448 KB Output is correct
6 Correct 1277 ms 116428 KB Output is correct
7 Correct 1306 ms 116444 KB Output is correct
8 Incorrect 1383 ms 116400 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 17 ms 1008 KB Output is correct
8 Correct 15 ms 1008 KB Output is correct
9 Correct 19 ms 1012 KB Output is correct
10 Correct 15 ms 1108 KB Output is correct
11 Correct 17 ms 1108 KB Output is correct
12 Correct 18 ms 1108 KB Output is correct
13 Correct 14 ms 1080 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 272 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 725 ms 116420 KB Output is correct
7 Correct 784 ms 116404 KB Output is correct
8 Correct 1010 ms 116400 KB Output is correct
9 Incorrect 1105 ms 116508 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 57 ms 3032 KB Output is correct
7 Correct 143 ms 14392 KB Output is correct
8 Correct 541 ms 116340 KB Output is correct
9 Correct 571 ms 116400 KB Output is correct
10 Correct 677 ms 116444 KB Output is correct
11 Correct 705 ms 116408 KB Output is correct
12 Correct 738 ms 116532 KB Output is correct
13 Correct 864 ms 116448 KB Output is correct
14 Correct 829 ms 116388 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 252 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 4 ms 852 KB Output is correct
21 Correct 92 ms 5508 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 4 ms 852 KB Output is correct
24 Correct 88 ms 5556 KB Output is correct
25 Correct 111 ms 5488 KB Output is correct
26 Correct 126 ms 5632 KB Output is correct
27 Correct 90 ms 5584 KB Output is correct
28 Correct 148 ms 14284 KB Output is correct
29 Incorrect 1673 ms 116452 KB Output isn't correct
30 Halted 0 ms 0 KB -