Submission #1232577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232577		kaiboy	Demarcation (BOI14_demarcation)	C++20	12 / 100	13 ms	3144 KiB

demarcation

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000;

int xx[N], yy[N], zz[N], aa0[N], aa1[N];

bool check(int *aa, int *bb, int n) {
	static int cc[N * 3], zz[N * 3];
	int m = 0;
	for (int i = 0; i < n; i++)
		cc[m++] = aa[i];
	for (int i = 0; i < n; i++)
		cc[m++] = bb[i];
	for (int i = 0; i < n; i++)
		cc[m++] = bb[i];
	for (int l = 0, r = 0, i = 1; i < m; i++)
		if (i + zz[i - l] < r)
			zz[i] = zz[i - l];
		else {
			r = max(r, l = i);
			while (r < m && cc[r] == cc[r - l])
				r++;
			zz[i] = r - l;
		}
	for (int i = n; i < m; i++)
		if (zz[i] >= n)
			return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> xx[i] >> yy[i];
	for (int flip = 1; flip >= 0; flip--) {
		for (int i = 0; i < n; i++)
			swap(xx[i], yy[i]);
		int i_ = 0;
		for (int i = 1; i < n; i++)
			if (yy[i_] > yy[i] || yy[i_] == yy[i] && xx[i_] < xx[i])
				i_ = i;
		for (int i = 0; i < n; i++)
			zz[i] = xx[(i_ + i) % n];
		for (int i = 0; i < n; i++)
			xx[i] = zz[i];
		for (int i = 0; i < n; i++)
			zz[i] = yy[(i_ + i) % n];
		for (int i = 0; i < n; i++)
			yy[i] = zz[i];
		if (yy[0] != yy[1]) {
			reverse(xx + 1, xx + n);
			reverse(yy + 1, yy + n);
		}
		long long s_ = 0;
		for (int i = 0; i < n; i++) {
			int j = (i + 1) % n;
			s_ += zz[i] = abs(xx[j] - xx[i]) + abs(yy[j] - yy[i]);
		}
		if (s_ % 2) {
			cout << "NO\n";
			return 0;
		}
		int xl_ = -1, xr_ = -1, y_ = -1;
		long long s = 0;
		for (int i = 0, j = 0; i < n; s -= zz[i++]) {
			while (j % 2 == 0 || s + zz[j] < s_ / 2)
				s += zz[j], j = (j + 1) % n;
			if (i % 2)
				if (yy[i] < yy[(i + 1) % n]) {
					if (yy[j] < yy[(j + 1) % n])
						continue;
					int xl = xx[i], xr = xx[j];
					if (xl > xr)
						continue;
					int yl = yy[i], yr = yy[j] - s_ / 2 + s;
					if (yl > yr || (yr - yl) % 2)
						continue;
					int y = (yl + yr) / 2;
					if (y <= yy[(i + 1) % n] && y >= yy[(j + 1) % n] && (y_ == -1 || xr_ - xl_ > xr - xl))
						xl_ = xl, xr_ = xr, y_ = y;
				} else {
					if (yy[j] > yy[(j + 1) % n])
						continue;
					int xl = xx[j], xr = xx[i];
					if (xl > xr)
						continue;
					int yl = yy[j] + s_ / 2 - s, yr = yy[i];
					if (yl > yr || (yr - yl) % 2)
						continue;
					int y = (yl + yr) / 2;
					if (y <= yy[(j + 1) % n] && y >= yy[(i + 1) % n] && (y_ == -1 || xr_ - xl_ > xr - xl))
						xl_ = xl, xr_ = xr, y_ = y;
				}
		}
		if (y_ == -1)
			continue;
		int il0 = -1, ir0 = -1;
		for (int i = 0; i < n; i++)
			if (xx[i] == xx[(i + 1) % n]) {
				int yl = yy[i], yr = yy[(i + 1) % n];
				if (yl > yr)
					swap(yl, yr);
				if (yl <= y_ && y_ < yr)
					if (il0 == -1)
						il0 = i;
					else if (ir0 == -1)
						ir0 = i;
					else {
						ir0 = -1;
						break;
					}
			}
		if (ir0 == -1)
			continue;
		int k0 = 0;
		for (int i = il0; i != ir0; i = (i + 1) % n) {
			if (xx[i] == xx[(i + 1) % n]) {
				if (yy[i] < yy[(i + 1) % n]) {
					aa0[k0] = yy[(i + 1) % n] - max(yy[i], y_) << 1;
					if (xx[(i + 2) % n] > xx[i])
						aa0[k0] ^= 1;
				} else {
					aa0[k0] = yy[i] - max(yy[(i + 1) % n], y_) << 1;
					if (xx[(i + 2) % n] < xx[i])
						aa0[k0] ^= 1;
				}
			} else {
				if (xx[i] < xx[(i + 1) % n]) {
					aa0[k0] = xx[(i + 1) % n] - xx[i] << 1;
					if (yy[(i + 2) % n] < yy[i])
						aa0[k0] ^= 1;
				} else {
					aa0[k0] = xx[i] - xx[(i + 1) % n] << 1;
					if (yy[(i + 2) % n] > yy[i])
						aa0[k0] ^= 1;
				}
			}
			k0++;
		}
		aa0[k0++] = yy[ir0] - y_ << 1 ^ 1;
		aa0[k0++] = xx[ir0] - xx[il0] << 1 ^ 1;
		int il1 = -1, ir1 = -1;
		for (int i = n - 1; i >= 0; i--)
			if (xx[i] == xx[(i + 1) % n]) {
				int yl = yy[i], yr = yy[(i + 1) % n];
				if (yl > yr)
					swap(yl, yr);
				if (yl < y_ && y_ <= yr)
					if (il1 == -1)
						il1 = i;
					else if (ir1 == -1)
						ir1 = i;
					else {
						ir1 = -1;
						break;
					}
			}
		if (ir1 == -1)
			continue;
		int k1 = 0;
		for (int i = il1; i != ir1; i = (i + 1) % n) {
			if (xx[i] == xx[(i + 1) % n]) {
				if (yy[i] < yy[(i + 1) % n]) {
					aa1[k1] = min(yy[(i + 1) % n], y_) - yy[i] << 1;
					if (xx[(i + 2) % n] > xx[i])
						aa1[k1] ^= 1;
				} else {
					aa1[k1] = min(yy[i], y_) - yy[(i + 1) % n] << 1;
					if (xx[(i + 2) % n] < xx[i])
						aa1[k1] ^= 1;
				}
			} else {
				if (xx[i] < xx[(i + 1) % n]) {
					aa1[k1] = xx[(i + 1) % n] - xx[i] << 1;
					if (yy[(i + 2) % n] < yy[i])
						aa1[k1] ^= 1;
				} else {
					aa1[k1] = xx[i] - xx[(i + 1) % n] << 1;
					if (yy[(i + 2) % n] > yy[i])
						aa1[k1] ^= 1;
				}
			}
			k1++;
		}
		aa1[k1++] = y_ - yy[ir1] << 1 ^ 1;
		aa1[k1++] = xx[il1] - xx[ir1] << 1 ^ 1;
		if (k0 != k1)
			continue;
		if (check(aa0, aa1, k0)) {
			if (!flip)
				cout << xl_ << ' ' << y_ << ' ' << xr_ << ' ' << y_ << '\n';
			else
				cout << y_ << ' ' << xl_ << ' ' << y_ << ' ' << xr_ << '\n';
			return 0;
		}
		reverse(aa1, aa1 + k1);
		int a = aa1[0] & 1;
		for (int h = 0; h + 1 < k1; h++)
			aa1[h] = aa1[h] & ~1 ^ aa1[h + 1] & 1;
		aa1[k1 - 1] = aa1[k1 - 1] & ~1 ^ a;
		if (check(aa0, aa1, k0)) {
			if (!flip)
				cout << xl_ << ' ' << y_ << ' ' << xr_ << ' ' << y_ << '\n';
			else
				cout << y_ << ' ' << xl_ << ' ' << y_ << ' ' << xr_ << '\n';
			return 0;
		}
	}
	cout << "NO\n";
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 23
• Subtask 4: 0 / 50