Submission #779323

#	Time	Username	Problem	Language	Result	Execution time	Memory
779323		Josia	Comparing Plants (IOI20_plants)	C++17	14 / 100	4064 ms	9680 KiB

plants

#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 (stderr)

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
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25