oj.uz

Submission #779343

# Submission time Handle Problem Language Result Execution time Memory
779343 2023-07-11T10:56:16 Z Josia Comparing Plants (IOI20_plants) C++17
0 / 100
 55 ms 3444 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) {
			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;
			}
		} 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 1 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 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 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 0 ms 212 KB Output is correct
3 Incorrect 55 ms 3444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 Incorrect 1 ms 296 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 1 ms 212 KB Output is correct
3 Incorrect 1 ms 260 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 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 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -