oj.uz

Submission #1050446

# Submission time Handle Problem Language Result Execution time Memory
1050446 2024-08-09T09:40:57 Z MercubytheFirst Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 5976 KB 
#include <bits/stdc++.h>
#include "plants.h"
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
using namespace std;
	
int n;
vector<int> group, big;
void init(int k, std::vector<int> r) {
	big = r;
	n = r.size();
	group.assign(n, -1);
	vector<bool> used(n), waiting(n);
	for(int round = 0; round < n; ++round) {
		waiting.assign(n, false);
		int nonzero = 0;
		vector<int> cur;
		for(int idx = 0; idx < 2*n; ++idx) {
			int i = idx % n;
			if(used[i]) {
				// assert(big[i] <= 0);
				nonzero += 1;
				continue;
			}
			else if(big[i] > 0) {
				nonzero += 1;
			}
			else if(big[i] == 0) {
				if(waiting[i]) {
					nonzero = 0;
					continue;
				}
				if(nonzero >= k - 1) {
					// used[i] = true;
					waiting[i] = true;
					group[i] = round;
					cur.push_back(i);
				}
				nonzero = 0;
			}
			// else assert(false);
		}
		for(int x : cur) {
			used[x] = true;
			big[x]--;
			int start_idx = (x + n - k + 1) % n;
			for(int i = start_idx; i != x; i = (i + 1) % n) {
				// assert(used[i] or big[i] != 0);
				big[i]--;
			}
		}
	}
	// for(int x : group)
	// 	cout << x << ' ';
	// cout << endl;

}
	
int compare_plants(int x, int y) {
	// assert(group[x] != -1 and group[y] != -1);
	if(group[x] < group[y]) {
		return 1;
	}
	else if(group[x] > group[y]) {
		return -1;
	}
	else {
		assert(group[x] == group[y]);
		return 0;
	}
}
	
	
	
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
	os << "[";
	for(size_t i = 0; i + 1 < N; ++i) {
		os << a[i] << ", ";
	}
	if(N > 0)
		os << a[N - 1];
	os << "]";
	return os;
}
	
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
	os << "(" << p.first << ", " << p.second << ") ";
	return os;
}
	
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
	os << '[';
	for(auto x : v)
		os << x << ", ";
	os << "] ";
	return os;
}
	
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
	os << "{";
	for(auto x : s)
		os << x << ", ";
	os << "} ";
	return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
	os << "{";
	for(auto x : s)
		os << x << ", ";
	os << "} ";
	return os;
}
	
	
/*
7 4 5
1 0 0 0 1 2 3
0 1
0 2
0 3
3 4
4 5

4 2 2
0 1 0 1
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 229 ms 3112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 500 KB Output is correct
10 Correct 231 ms 3156 KB Output is correct
11 Correct 184 ms 3112 KB Output is correct
12 Correct 182 ms 3408 KB Output is correct
13 Correct 260 ms 3112 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 229 ms 3112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 500 KB Output is correct
10 Correct 231 ms 3156 KB Output is correct
11 Correct 184 ms 3112 KB Output is correct
12 Correct 182 ms 3408 KB Output is correct
13 Correct 260 ms 3112 KB Output is correct
14 Correct 3285 ms 3352 KB Output is correct
15 Execution timed out 4086 ms 5976 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 43 ms 3060 KB Output is correct
4 Execution timed out 4035 ms 5716 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -