oj.uz

Submission #779360

# Submission time Handle Problem Language Result Execution time Memory
779360 2023-07-11T11:12:04 Z Josia Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 12596 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 segtree {
	vector<int> tree;
	void init(int N) {
		tree.assign(N*4, 0);
	}
	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {tree[v] = x; return;}
		int rm = (rl + rr)/2;

		if (pos<=rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);
		tree[v] = tree[v*2] + tree[v*2+1];
	}
	int query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return 0;
		if (rl == ql && rr == qr) return tree[v];
		int rm = (rl + rr) / 2;
		return query(v*2, rl, rm, ql, min(qr, rm)) + query(v*2+1, rm+1, rr, max(ql, rm+1), qr);
	}
};



segtree blub1, blub2;








struct findExtrema {
	vector<int> findMax() {
		vector<int> mins;
		int last = 0;
		for (int i = 0; i<n; i++) {
			// cerr << last << "\n";
			if (bigger[i]-blub1.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub1.query(1, 0, n-1, 0, (i+k-1)%n):0) == 0 && last >= k) {mins.push_back(i);}
			if (bigger[i]-blub1.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub1.query(1, 0, n-1, 0, (i+k-1)%n):0) == 0) last = 0;
			last++;
		}
		for (int i = 0; i<n; i++) {
			// cerr << last << "\n";
			if (bigger[i]-blub1.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub1.query(1, 0, n-1, 0, (i+k-1)%n):0) == 0 && last >= k) {mins.push_back(i);}
			if (bigger[i]-blub1.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub1.query(1, 0, n-1, 0, (i+k-1)%n):0) == 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]-blub2.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub2.query(1, 0, n-1, 0, (i+k-1)%n):0) == 0 && last >= k) {maxs.push_back(i);}
			if (smaller[i]-blub2.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub2.query(1, 0, n-1, 0, (i+k-1)%n):0) == 0) last = 0;
			last++;
		}
		for (int i = 0; i<n; i++) {
			if (smaller[i]-blub2.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub2.query(1, 0, n-1, 0, (i+k-1)%n):0) == 0 && last >= k) {maxs.push_back(i);}
			if (smaller[i]-blub2.query(1, 0, n-1, i, min(n-1,i+k-1))-(i+k-1>=n?blub2.query(1, 0, n-1, 0, (i+k-1)%n):0) == 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) {
		blub1.init(n);
		blub2.init(n);
		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;
				blub1.update(1, 0, n-1, i, 1);
				// 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;
				blub2.update(1, 0, n-1, i, 1);
				// 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 not connected return zero
		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 (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:170: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]
  170 |  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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 458 ms 440 KB Output is correct
7 Execution timed out 4030 ms 3568 KB Time limit exceeded
8 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 458 ms 440 KB Output is correct
7 Execution timed out 4030 ms 3568 KB Time limit exceeded
8 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 300 KB Output is correct
3 Correct 708 ms 3760 KB Output is correct
4 Execution timed out 4075 ms 12596 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 212 KB Output is correct
2 Correct 1 ms 300 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 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 300 KB Output isn't correct
5 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 -