oj.uz

Submission #824110

# Submission time Handle Problem Language Result Execution time Memory
824110 2023-08-13T14:21:27 Z thimote75 Comparing Plants (IOI20_plants) C++14
44 / 100
 493 ms 19816 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

using idata = vector<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);
		dbg(i, value);

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

			tree[i].merge(tree[i * 2], tree[i * 2 + 1]);
		}
	}
	void modify (int l, int r, int value) {
		dbg(l, r, 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);
	}
};

void init(int k, idata r) {
	K = k;

	idata r0 = r;
	int n = r.size();

	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);

	return;
}

int compare_plants(int x, int y) {
	int del = A[x] - A[y];
	if (del == 0) return 0;
	return del / abs(del);
}

Compilation message

plants.cpp: In function 'void shift(idata&, int)':
plants.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = count; i < r.size(); i ++)
      |                      ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, idata)':
plants.cpp:172:6: warning: unused variable 's' [-Wunused-variable]
  172 |  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 Incorrect 0 ms 212 KB Output isn't correct
5 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 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 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 53 ms 3124 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 47 ms 3108 KB Output is correct
11 Correct 46 ms 3104 KB Output is correct
12 Correct 45 ms 3248 KB Output is correct
13 Correct 48 ms 3208 KB Output is correct

Subtask #3
13.0 / 13.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 0 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 53 ms 3124 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 47 ms 3108 KB Output is correct
11 Correct 46 ms 3104 KB Output is correct
12 Correct 45 ms 3248 KB Output is correct
13 Correct 48 ms 3208 KB Output is correct
14 Correct 76 ms 4244 KB Output is correct
15 Correct 492 ms 16052 KB Output is correct
16 Correct 74 ms 6460 KB Output is correct
17 Correct 493 ms 19796 KB Output is correct
18 Correct 315 ms 19344 KB Output is correct
19 Correct 289 ms 19800 KB Output is correct
20 Correct 487 ms 19816 KB Output is correct

Subtask #4
17.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 42 ms 3200 KB Output is correct
4 Correct 188 ms 15948 KB Output is correct
5 Correct 277 ms 19132 KB Output is correct
6 Correct 377 ms 19276 KB Output is correct
7 Correct 439 ms 19520 KB Output is correct
8 Correct 482 ms 19644 KB Output is correct
9 Correct 227 ms 19068 KB Output is correct
10 Correct 227 ms 19000 KB Output is correct
11 Correct 129 ms 18864 KB Output is correct
12 Correct 215 ms 19156 KB Output is correct
13 Correct 297 ms 19188 KB Output is correct

Subtask #5
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 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 Incorrect 0 ms 212 KB Output isn't correct
4 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 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -