Submission #839212

#	Time	Username	Problem	Language	Result	Execution time	Memory
839212		tranxuanbach	Comparing Plants (IOI20_plants)	C++17	0 / 100	1 ms	312 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

const int N = 2e5 + 5;

int n, k;
int a[N];

namespace subtask1{
	int checked = -1;

	bool check(){
		if (checked >= 0){
			return checked;
		}
		return (checked = (k == 2));
	}

	pair <int, int> pre[N], nxt[N];

	void init(){
		for (int turn = 0; turn < 2; turn++){
			for (int i = 0; i < n; i++){
				int j = (i + n - 1) % n;
				if (a[(j + n - 1) % n] == a[j]){
					pre[i] = pair{pre[j].first, pre[j].second};
				}
				else{
					pre[i] = pair{j, a[j] == 1 ? 1 : -1};
				}
			}
			for (int i = n - 1; i >= 0; i--){
				int j = (i + 1) % n;
				if (a[(j + 1) % n] == a[j]){
					nxt[i] = pair{nxt[j].first, nxt[j].second};
				}
				else{
					nxt[i] = pair{j, a[i] == 1 ? -1 : 1};
				}
			}
		}
	}

	bool in_circular_range(int l, int r, int i){
		if (l <= r){
			return l <= i and i <= r;
		}
		else{
			return l <= i or i <= r;
		}
	}

	int solve(int x, int y){
		if (in_circular_range(pre[x].first, x, y)){
			return pre[x].second;
		}
		if (in_circular_range(x, nxt[x].first, y)){
			return nxt[x].second;
		}
		return 0;
	}
}

void init(int _k, vector <int> _a){
	n = isz(_a);
	k = _k;
	for (int i = 0; i < n; i++){
		a[i] = _a[i];
	}
	if (subtask1::check()){
		subtask1::init();
	}
	return;
}

int compare_plants(int x, int y){
	if (subtask1::check()){
		return subtask1::solve(x, y);
	}
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25