oj.uz

Submission #825236

# Submission time Handle Problem Language Result Execution time Memory
825236 2023-08-14T16:02:39 Z thimote75 Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 20540 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using iset  = set<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);
	}
};

idata lw, rw;

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);
	}
 
	dbg(A);

	lw.resize(N, -1);
	rw.resize(N, -1);
	dbg(lw, rw);
 
	for (int i = 0; i < N; i ++) {
		for (int j = i - K + 1; j < i; j ++) {
			int rj = (j + N) % N;
			if (A[rj] >= A[i]) continue ;
			if (lw[i] != -1) {
				if (A[lw[i]] >= A[rj]) continue ;
			}

			lw[i] = rj;
		}

		for (int j = i + K - 1; j > i; j --) {
			int rj = j % N;
			if (A[rj] >= A[i]) continue ;
			if (rw[i] != -1) {
				if (A[rw[i]] >= A[rj]) continue ;
			}

			rw[i] = rj;
		}
	}

	dbg(lw);
	dbg(rw);

	return;
}

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

	return min(b - a, N + a - b);
}
bool dfs (idata &V, int s, int t) {
	if (s == -1) return false;
	if (distance(s, t) < K)
		return A[s] > A[t];
	return dfs(V, V[s], t);
}
bool dfs (int s, int t) {
	return dfs(lw, s, t) || dfs(rw, s, t);
}
 
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:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = count; i < r.size(); i ++)
      |                      ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, idata)':
plants.cpp:173:6: warning: unused variable 's' [-Wunused-variable]
  173 |  int s = 0;
      |      ^

Subtask #1
0 / 5.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 0 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 50 ms 3984 KB Output is correct
7 Correct 133 ms 6572 KB Output is correct
8 Correct 164 ms 20428 KB Output is correct
9 Correct 220 ms 20540 KB Output is correct
10 Correct 799 ms 20532 KB Output is correct
11 Execution timed out 4070 ms 20428 KB Time limit exceeded
12 Halted 0 ms 0 KB -

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 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 12 ms 420 KB Output is correct
7 Correct 306 ms 3148 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 12 ms 416 KB Output is correct
10 Correct 288 ms 3224 KB Output is correct
11 Correct 158 ms 3092 KB Output is correct
12 Correct 154 ms 3272 KB Output is correct
13 Correct 367 ms 3144 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 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 12 ms 420 KB Output is correct
7 Correct 306 ms 3148 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 12 ms 416 KB Output is correct
10 Correct 288 ms 3224 KB Output is correct
11 Correct 158 ms 3092 KB Output is correct
12 Correct 154 ms 3272 KB Output is correct
13 Correct 367 ms 3144 KB Output is correct
14 Correct 2701 ms 4408 KB Output is correct
15 Execution timed out 4078 ms 17584 KB Time limit exceeded
16 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 265 ms 3152 KB Output is correct
4 Execution timed out 4097 ms 17508 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 256 KB Output is correct
4 Correct 1 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 13 ms 1188 KB Output is correct
8 Correct 13 ms 1160 KB Output is correct
9 Correct 19 ms 1212 KB Output is correct
10 Correct 17 ms 1292 KB Output is correct
11 Correct 14 ms 1236 KB Output is correct
12 Correct 14 ms 1192 KB Output is correct
13 Correct 12 ms 1236 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 0 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 733 ms 19836 KB Output is correct
7 Correct 3348 ms 20036 KB Output is correct
8 Execution timed out 4070 ms 20200 KB Time limit exceeded
9 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 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 0 ms 300 KB Output is correct
6 Correct 50 ms 3984 KB Output is correct
7 Correct 133 ms 6572 KB Output is correct
8 Correct 164 ms 20428 KB Output is correct
9 Correct 220 ms 20540 KB Output is correct
10 Correct 799 ms 20532 KB Output is correct
11 Execution timed out 4070 ms 20428 KB Time limit exceeded
12 Halted 0 ms 0 KB -