oj.uz

Submission #302934

# Submission time Handle Problem Language Result Execution time Memory
302934 2020-09-19T12:59:39 Z 8e7 Comparing Plants (IOI20_plants) C++14
5 / 100
 116 ms 8684 KB 
#include "plants.h"
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> v, one, zero, ind1, ind0;
int k;
int n;
void init(int K, vector<int> r) {
	v = r;
	n = r.size();
	int cnt = 0, cur = 0;
	one.push_back(cnt);
	for (int i = 0;i < n;i++) {
		if (r[i] == 0) {
			ind1.push_back(cur);
			cur = i + 1;
			cnt++;
		}
		one.push_back(cnt);
	}
	if (r[n - 1] == 1) {
		for (int i = n - 1;i >= 0;i--) {
			if (one[i] == cnt) ind1[0] = i;
			one[i] %= cnt;
		}
	}
	cnt = 0, cur = 0;
	zero.push_back(cnt);
	for (int i = 0;i < n;i++) {
		if (r[i] == 1) {
			ind0.push_back(cur);
			cur = i + 1;
			cnt++;
		}
		zero.push_back(cnt);
	}
	if (r[n - 1] == 0) {
		for (int i = n - 1;i >= 0;i--) {
			if (zero[i] == cnt) ind0[0] = i;
			zero[i] %= cnt;
		}
	}
	k = K;
	/*
	for (int i = 0;i < n;i++) cout << one[i] << " ";
	cout << endl;
	for (int i:ind1) cout << i << " ";
	cout << endl;
	for (int i = 0;i < n;i++) cout << zero[i] << " ";
	cout << endl;
	for (int i:ind0) cout << i << " ";
	cout << endl;
	*/
	return;
}

int compare_plants(int x, int y) {
	if (one[x] != one[y] && zero[x] != zero[y]) {
		return 0;
	} else {
		if (one[x] == one[y]) {
			//cout <<(x - ind1[one[x]] + n) % n << " " << (y - ind1[one[y]] + n) % n << endl;
			if ((x - ind1[one[x]] + n) % n < (y - ind1[one[y]] + n) % n) return -1;
			else return 1;
		} else {
			if ((x - ind0[zero[x]] + n) % n < (y - ind0[zero[y]] + n) % n) return 1;
			else return -1;
		}
	}
}
/*
5 1 3
1 1 0 0 1
0 1
0 3
2 4
 */

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 67 ms 3192 KB Output is correct
7 Correct 87 ms 3832 KB Output is correct
8 Correct 116 ms 8428 KB Output is correct
9 Correct 115 ms 8684 KB Output is correct
10 Correct 116 ms 8040 KB Output is correct
11 Correct 116 ms 8040 KB Output is correct
12 Correct 112 ms 7924 KB Output is correct
13 Correct 108 ms 8164 KB Output is correct
14 Correct 110 ms 8172 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 1 ms 256 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 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 67 ms 3192 KB Output is correct
7 Correct 87 ms 3832 KB Output is correct
8 Correct 116 ms 8428 KB Output is correct
9 Correct 115 ms 8684 KB Output is correct
10 Correct 116 ms 8040 KB Output is correct
11 Correct 116 ms 8040 KB Output is correct
12 Correct 112 ms 7924 KB Output is correct
13 Correct 108 ms 8164 KB Output is correct
14 Correct 110 ms 8172 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Incorrect 0 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -