oj.uz

Submission #825262

# Submission time Handle Problem Language Result Execution time Memory
825262 2023-08-14T16:27:33 Z thimote75 Comparing Plants (IOI20_plants) C++14
30 / 100
 1290 ms 204980 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) 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 1 ms 212 KB Output is correct
2 Correct 0 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 1 ms 212 KB Output is correct
6 Correct 53 ms 3992 KB Output is correct
7 Correct 166 ms 15676 KB Output is correct
8 Correct 540 ms 117620 KB Output is correct
9 Correct 595 ms 117708 KB Output is correct
10 Correct 634 ms 117748 KB Output is correct
11 Correct 736 ms 117748 KB Output is correct
12 Correct 772 ms 119248 KB Output is correct
13 Correct 801 ms 119348 KB Output is correct
14 Correct 779 ms 119244 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 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 1 ms 340 KB Output is correct
6 Correct 4 ms 880 KB Output is correct
7 Correct 85 ms 6864 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 85 ms 6812 KB Output is correct
11 Correct 107 ms 6772 KB Output is correct
12 Correct 129 ms 6944 KB Output is correct
13 Correct 87 ms 6788 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 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 1 ms 340 KB Output is correct
6 Correct 4 ms 880 KB Output is correct
7 Correct 85 ms 6864 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 85 ms 6812 KB Output is correct
11 Correct 107 ms 6772 KB Output is correct
12 Correct 129 ms 6944 KB Output is correct
13 Correct 87 ms 6788 KB Output is correct
14 Correct 148 ms 15564 KB Output is correct
15 Runtime error 1032 ms 203260 KB Execution killed with signal 11
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 1 ms 212 KB Output is correct
3 Correct 107 ms 4180 KB Output is correct
4 Correct 1106 ms 117656 KB Output is correct
5 Correct 1110 ms 119476 KB Output is correct
6 Correct 1290 ms 119480 KB Output is correct
7 Correct 1285 ms 119516 KB Output is correct
8 Runtime error 984 ms 204980 KB Execution killed with signal 11
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 0 ms 212 KB Output is correct
4 Correct 1 ms 300 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 1364 KB Output is correct
8 Correct 14 ms 1328 KB Output is correct
9 Correct 23 ms 1404 KB Output is correct
10 Correct 14 ms 1364 KB Output is correct
11 Correct 17 ms 1328 KB Output is correct
12 Correct 17 ms 1328 KB Output is correct
13 Correct 14 ms 1332 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 757 ms 117692 KB Output is correct
7 Correct 782 ms 117680 KB Output is correct
8 Correct 1016 ms 117740 KB Output is correct
9 Runtime error 972 ms 204740 KB Execution killed with signal 11
10 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 0 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 1 ms 212 KB Output is correct
6 Correct 53 ms 3992 KB Output is correct
7 Correct 166 ms 15676 KB Output is correct
8 Correct 540 ms 117620 KB Output is correct
9 Correct 595 ms 117708 KB Output is correct
10 Correct 634 ms 117748 KB Output is correct
11 Correct 736 ms 117748 KB Output is correct
12 Correct 772 ms 119248 KB Output is correct
13 Correct 801 ms 119348 KB Output is correct
14 Correct 779 ms 119244 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 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 880 KB Output is correct
21 Correct 85 ms 6864 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 4 ms 852 KB Output is correct
24 Correct 85 ms 6812 KB Output is correct
25 Correct 107 ms 6772 KB Output is correct
26 Correct 129 ms 6944 KB Output is correct
27 Correct 87 ms 6788 KB Output is correct
28 Correct 148 ms 15564 KB Output is correct
29 Runtime error 1032 ms 203260 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -