oj.uz

Submission #779323

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

#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, int>> useToCalc;


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


	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 < (int)(useToCalc.size())-1) {
			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:130: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]
  130 |  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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 276 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 1 ms 300 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 305 ms 5336 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 14 ms 436 KB Output is correct
10 Correct 301 ms 5360 KB Output is correct
11 Correct 251 ms 5296 KB Output is correct
12 Correct 255 ms 5504 KB Output is correct
13 Correct 333 ms 5396 KB Output is correct

Subtask #3
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 1 ms 300 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 305 ms 5336 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 14 ms 436 KB Output is correct
10 Correct 301 ms 5360 KB Output is correct
11 Correct 251 ms 5296 KB Output is correct
12 Correct 255 ms 5504 KB Output is correct
13 Correct 333 ms 5396 KB Output is correct
14 Correct 3665 ms 6816 KB Output is correct
15 Execution timed out 4042 ms 9680 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 1 ms 212 KB Output is correct
3 Correct 63 ms 4956 KB Output is correct
4 Execution timed out 4064 ms 8908 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 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 1 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 276 KB Output isn't correct
5 Halted 0 ms 0 KB -