oj.uz

Submission #1050468

# Submission time Handle Problem Language Result Execution time Memory
1050468 2024-08-09T09:55:09 Z MercubytheFirst Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 5884 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]) {
					break;
				}
				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 1 ms 348 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 252 ms 3116 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 227 ms 3124 KB Output is correct
11 Correct 177 ms 3108 KB Output is correct
12 Correct 173 ms 3408 KB Output is correct
13 Correct 259 ms 3240 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 252 ms 3116 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 227 ms 3124 KB Output is correct
11 Correct 177 ms 3108 KB Output is correct
12 Correct 173 ms 3408 KB Output is correct
13 Correct 259 ms 3240 KB Output is correct
14 Correct 3437 ms 3356 KB Output is correct
15 Execution timed out 4022 ms 5716 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 348 KB Output is correct
3 Correct 58 ms 3156 KB Output is correct
4 Execution timed out 4051 ms 5884 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 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 1 ms 348 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 -