oj.uz

Submission #779327

# Submission time Handle Problem Language Result Execution time Memory
779327 2023-07-11T10:32:22 Z Josia Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 6148 KB 
#include "plants.h"

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> bigger, smaller;

vector<pair<int, int>> useToCalc;

int numgroups;


struct findExtrema {
	vector<int> findMax() {
		vector<int> mins;
		int last = 0;
		for (int i = 0; i<n; i++) {
			// cerr << last << "\n";
			if (bigger[i] == 0 && last >= k) {mins.push_back(i);}
			if (bigger[i] == 0) last = 0;
			last++;
		}
		for (int i = 0; i<n; i++) {
			// cerr << last << "\n";
			if (bigger[i] == 0 && last >= k) {mins.push_back(i);}
			if (bigger[i] == 0) last = 0;
			last++;
		}
		sort(mins.begin(), mins.end());
		mins.erase(unique(mins.begin(),mins.end()), mins.end());

		return mins;
	}

	vector<int> findMin() {
		vector<int> maxs;
		int last = 0;
		for (int i = 0; i<n; i++) {
			if (smaller[i] == 0 && last >= k) {maxs.push_back(i);}
			if (smaller[i] == 0) last = 0;
			last++;
		}
		for (int i = 0; i<n; i++) {
			if (smaller[i] == 0 && last >= k) {maxs.push_back(i);}
			if (smaller[i] == 0) last = 0;
			last++;
		}
		sort(maxs.begin(), maxs.end());
		maxs.erase(unique(maxs.begin(),maxs.end()), maxs.end());

		return maxs;
	}
};



struct makeGroups {
	vector<pair<vector<int>, vector<int>>> groups;
	makeGroups(int x) {
		groups.clear();


		while (true) {
			// cerr << "---\n";
			// for (int i = 0; i<n; i++) {
			// 	cerr << bigger[i] << " " << smaller[i] << "\n";
			// }
			// cerr << "---\n";
			findExtrema machine;

			vector<int> mins = machine.findMin();
			vector<int> maxs = machine.findMax();

			if (mins.empty() && maxs.empty()) break;
			groups.push_back({mins, maxs});

			for (int i: maxs) {
				bigger[i] = 1e9;
				smaller[i] = 1e9;
				for (int j = i-1; j>i-k; j--) {
					if (bigger[(j+n)%n]!=1e9) bigger[(j+n)%n]--;
				}
			}

			for (int i: mins) {
				bigger[i] = 1e9;
				smaller[i] = 1e9;
				for (int j = i-1; j>i-k; j--) {
					if (smaller[(j+n)%n]!=1e9) smaller[(j+n)%n]--;
				}
			}
		}
	}	
};





void init(int K, std::vector<int> r) {
	n = r.size();
	k = K;
	smaller.assign(n,0);
	bigger = r;

	for (int i = 0; i<n; i++) {
		smaller[i] = k-1-bigger[i];
	}


	makeGroups groups(0);

	// for (auto i: groups.groups) {
	// 	for (auto j: i.first) {
	// 		cerr << j << " ";
	// 	}
	// 	cerr << "   ---   ";
	// 	for (auto j: i.second) {
	// 		cerr << j << " ";
	// 	}
	// 	cerr << "\n";
	// }

	// cerr << "initDone\n";


	vector<pair<int, int>> plants(n, {-1, -1});	// which group, 0min/1max/2both

	numgroups = groups.groups.size();

	for (int ind = 0; ind < groups.groups.size(); ind++) {
		auto i = groups.groups[ind];
		for (auto j: i.first) {
			plants[j] = {ind, 0};
		}
		for (auto j: i.second) {
			plants[j] = {ind, plants[j].second==-1?1:2};
		}
	}

	useToCalc = plants;

	return;
}

int compare_plants(int x, int y) {
	int g1 = useToCalc[x].first;
	int g2 = useToCalc[y].first;


	if (g1!=g2) {
		if (g1<g2) {
			if (useToCalc[x].second == 0) return -1;
			else return 1;
		}
		else {
			if (useToCalc[y].second == 0) return 1;
			else return -1;
		}
	} else {
		if (g1 < numgroups-1) {
			// cerr << g1 << " " << (int)(useToCalc.size())-1 << "\n";
			// cerr << "   weee" << " " << x << " " << y << "\n";
			if (useToCalc[x].second == useToCalc[y].second) return 0;
			if (useToCalc[x].second < useToCalc[y].second) return -1;
			if (useToCalc[x].second > useToCalc[y].second) return 1;
		} else {
			if (abs(x-y)<k) {
				if (useToCalc[x].second == useToCalc[y].second) assert(0);
				if (useToCalc[x].second < useToCalc[y].second) return -1;
				if (useToCalc[x].second > useToCalc[y].second) return 1;
			} else {
				return 0;
			}
		}
	}


	return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:133:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::vector<int>, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for (int ind = 0; ind < groups.groups.size(); ind++) {
      |                    ~~~~^~~~~~~~~~~~~~~~~~~~~~

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 1 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 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 460 KB Output is correct
7 Correct 295 ms 3560 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 12 ms 440 KB Output is correct
10 Correct 292 ms 3596 KB Output is correct
11 Correct 234 ms 3560 KB Output is correct
12 Correct 233 ms 3636 KB Output is correct
13 Correct 328 ms 3524 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 460 KB Output is correct
7 Correct 295 ms 3560 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 12 ms 440 KB Output is correct
10 Correct 292 ms 3596 KB Output is correct
11 Correct 234 ms 3560 KB Output is correct
12 Correct 233 ms 3636 KB Output is correct
13 Correct 328 ms 3524 KB Output is correct
14 Correct 3579 ms 4612 KB Output is correct
15 Execution timed out 4037 ms 6148 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 53 ms 3284 KB Output is correct
4 Execution timed out 4064 ms 6048 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 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 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 Incorrect 0 ms 212 KB Output isn't correct
5 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 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -