Submission #1061295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061295		jhwest2	Demarcation (BOI14_demarcation)	C++17	0 / 100	8 ms	2324 KiB

demarcation

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct segment {
	int x, l, r, pos, dir; ll s, e;
	bool operator<(const segment &ot) const {
		return l < ot.l;
	}
};
bool operator<(const segment &s, const int &y) { return s.l < y; }
bool operator<(const int &y, const segment &s) { return y < s.l; }

int ccw(pii p, pii q, pii r) {
	ll x = 1ll * (q.ff - p.ff) * (r.ss - q.ss) - 1ll * (q.ss - p.ss) * (r.ff - q.ff);
	return (x > 0) - (x < 0);
}
bool cyclic_shift(vector<int> S, vector<int> T) {
	if (S.size() != T.size()) return false;
	int n = S.size();
	int F[n]{};
	for (int i = 1, p = 0; i < n; i++) {
		while (p > 0 && S[i] != S[p]) p = F[p - 1];
		if (S[i] == S[p]) ++p;
		F[i] = p;
	}
	T.resize(2 * n);
	for (int i = 0; i < n; i++) T[n + i] = T[i];
	for (int i = 0, p = 0; i < 2 * n; i++) {
		while (p > 0 && T[i] != S[p]) p = F[p - 1];
		if (T[i] == S[p]) ++p;
		if (p == n) return true;
	}
	return false;
}
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	int x[n], y[n], r[n];
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
	int minx = x[0], miny = y[0];
	for (int i = 1; i < n; i++) {
		minx = min(minx, x[i]);
		miny = min(miny, y[i]);
	}
	for (int i = 0; i < n; i++) x[i] -= minx, y[i] -= miny;
	ll tot = 0;
	for (int i = 0; i < n; i++) tot += abs(x[i] - x[(i + 1) % n]) + abs(y[i] - y[(i + 1) % n]);
	for (int dir = 0; dir < 2; dir++) {
		for (int i = 0; i < n; i++) {
			pii prv = {x[(i + n - 1) % n], y[(i + n - 1) % n]};
			pii cur = {x[i], y[i]};
			pii nxt = {x[(i + 1) % n], y[(i + 1) % n]};
			r[i] = ccw(prv, cur, nxt);
		}
		int det = accumulate(r, r + n, 0);
		// for (int i = 0; i < n; i++) cout << r[i] << ' ';
		// cout << det << endl;
		if (det < 0) {
			assert(det == -4);
			reverse(x, x + n);
			reverse(y, y + n);
			reverse(r, r + n);
			for (int i = 0; i < n; i++) r[i] *= -1;
		}
		else assert(det == 4);
		ll idx[n]{};
		for (int i = 1; i < n; i++) {
			idx[i] = idx[i - 1] + abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
		}
		// cout << dir << '\n';
		set<segment, less<>> ST;
		auto cut = [&](int l, int r) {
			auto it = ST.lower_bound(l);
			if (it != ST.begin()) {
				it = prev(it);
				segment tmp = *it;
				if (tmp.r >= l) {
					ST.erase(it);
					ll m1 = tmp.dir ? tmp.s + (l - 1 - tmp.l) : tmp.s - (l - 1 - tmp.l);
					ll m2 = tmp.dir ? m1 + 1 : m1 - 1;
					// m1 = (m1 % tot + tot) % tot;
					// m2 = (m2 % tot + tot) % tot;
					ST.insert({tmp.x, tmp.l, l - 1, tmp.pos, tmp.dir, tmp.s, m1});
					ST.insert({tmp.x, l, tmp.r, tmp.pos, tmp.dir, m2, tmp.e});
				}
			}
			it = ST.upper_bound(r);
			if (it != ST.begin()) {
				it = prev(it);
				segment tmp = *it;
				if (tmp.r > r) {
					ST.erase(it);
					ll m1 = tmp.dir ? tmp.s + (r - tmp.l) : tmp.s - (r - tmp.l);
					ll m2 = tmp.dir ? m1 + 1 : m1 - 1;
					// m1 = (m1 % tot + tot) % tot;
					// m2 = (m2 % tot + tot) % tot;
					ST.insert({tmp.x, tmp.l, r, tmp.pos, tmp.dir, tmp.s, m1});
					ST.insert({tmp.x, r + 1, tmp.r, tmp.pos, tmp.dir, m2, tmp.e});
				}
			}
		};
		vector<segment> S;
		for (int i = 0; i < n; i++) {
			int j = (i + 1) % n;
			if (x[i] == x[j]) {
				int dir = y[j] > y[i];
				int l, rr; ll s, e;
				if (dir) {
					l = r[i] < 0 ? y[i] : y[i] + 1;
					rr = r[j] < 0 ? y[j] : y[j] - 1;
				}
				else {
					l = r[i] < 0 ? y[i] : y[i] - 1;
					rr = r[j] < 0 ? y[j] : y[j] + 1;
				}
				s = r[i] < 0 ? idx[i] : idx[i] + 1;
				e = r[j] < 0 ? idx[j] : idx[j] - 1;
				if (!dir) {
					swap(l, rr);
					swap(s, e);
				}
				if (l <= rr) S.push_back({x[i], l, rr, i, dir, s, e});
				// cout << "raw segment x = " << x[i] << ", " << "y = [" << l << ", " << rr << "] , idx = " << s << ", " << e << '\n';
			}
		}
		sort(S.begin(), S.end(), [&](const segment &p, const segment &q) { return p.x < q.x; });
		vector<pair<segment, segment>> V;
		for (segment &s : S) {
			cut(s.l, s.r);
			auto it = ST.lower_bound(s.l);
			for (; it != ST.end() && it->l <= s.r; it = ST.erase(it)) {
				if (s.dir) {
					segment prv = *it;
					assert(!prv.dir);
					segment cur = {s.x, prv.l, prv.r, s.pos, s.dir, 0, 0};
					cur.s = s.s + (prv.l - s.l);
					cur.e = s.s + (prv.r - s.l);
					// cur.s %= tot;
					// cur.e %= tot;
					V.push_back({prv, cur});
					// cout << "two segments at [" << prv.l << ", " << prv.r << "] with x = " << prv.x << ", " << cur.x << "\n";
					// cout << "index L : " << prv.s << ", " << prv.e << '\n';
					// cout << "index R : " << cur.s << ", " << cur.e << '\n';
				}
			}
			ST.insert(s);
		}
		for (auto &[L, R] : V) {
			ll Y = L.e + L.r + R.l - R.s + tot / 2;
			Y = (Y % tot + tot) % tot;
			// cout << "two segments at [" << L.l << ", " << L.r << "] with x = " << L.x << ", " << R.x << "\n";
			// cout << "at Y = " << Y << '\n';
			if (Y % 2 != 0) continue;
			Y /= 2;
			if (max(L.l, R.l) <= Y && Y <= min(L.r, R.r)) {
				vector<int> S, T;
				{
					if (Y != y[R.pos]) {
						S.push_back(r[R.pos] > 0 ? -1 : -2);
						S.push_back(Y - y[R.pos]);
						S.push_back(-1);
					}
					S.push_back(R.x - L.x);
					if (Y != y[(L.pos + 1) % n]) {
						S.push_back(-1);
						S.push_back(Y - y[(L.pos + 1) % n]);
						S.push_back(r[(L.pos + 1) % n] > 0 ? -1 : -2);
					}
					for (int v = (L.pos + 1) % n; ; v = (v + 1) % n) {
						S.push_back(abs(x[v] - x[(v + 1) % n]) + abs(y[v] - y[(v + 1) % n]));
						if ((v + 1) % n == R.pos) {
							break;
						}
						S.push_back(r[(v + 1) % n] > 0 ? -1 : -2);
					}
					int pos = 0;
					while (S[pos] > 0) ++pos;
					rotate(S.begin(), S.begin() + pos, S.end());
					vector<int> V;
					for (int x : S) {
						if (V.empty() || V.back() < 0 || x < 0) V.push_back(x);
						else V.back() += x;
					}
					S = V;
				}
				{
					if (Y != y[L.pos]) {
						T.push_back(r[L.pos] > 0 ? -1 : -2);
						T.push_back(y[L.pos] - Y);
						T.push_back(-1);
					}
					T.push_back(R.x - L.x);
					if (Y != y[(R.pos + 1) % n]) {
						T.push_back(-1);
						T.push_back(y[(R.pos + 1) % n] - Y);
						T.push_back(r[(R.pos + 1) % n] > 0 ? -1 : -2);
					}
					for (int v = (R.pos + 1) % n; ; v = (v + 1) % n) {
						T.push_back(abs(x[v] - x[(v + 1) % n]) + abs(y[v] - y[(v + 1) % n]));
						if ((v + 1) % n == L.pos) {
							break;
						}
						T.push_back(r[(v + 1) % n] > 0 ? -1 : -2);
					}
					int pos = 0;
					while (T[pos] > 0) ++pos;
					rotate(T.begin(), T.begin() + pos, T.end());
					vector<int> V;
					for (int x : T) {
						if (V.empty() || V.back() < 0 || x < 0) V.push_back(x);
						else V.back() += x;
					}
					T = V;
				}
				// cout << "string S = [ ";
				// for (int x : S) cout << x << ' '; cout << "]\n";
				// cout << "string T = [ ";
				// for (int x : T) cout << x << ' '; cout << "]\n";
				bool flag = cyclic_shift(S, T);
				if (!flag) {
					reverse(S.begin(), S.end());
					flag = cyclic_shift(S, T);
				}
				if (flag) {
					if (!dir) {
						cout << L.x + minx << ' ' << Y + miny << ' ' << R.x + minx << ' ' << Y + miny << '\n';
					}
					else {
						cout << Y + miny << ' ' << L.x + minx << ' ' << Y + miny << ' ' << R.x + minx << '\n';
					}
					return 0;
				}
			}
		}
		for (int i = 0; i < n; i++) swap(x[i], y[i]);
	}
	cout << "NO\n";
}

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