Submission #208812

#	Time	Username	Problem	Language	Result	Execution time	Memory
208812		E869120	Demarcation (BOI14_demarcation)	C++14	100 / 100	275 ms	51284 KiB

demarcation

#include <iostream>
#include <vector>
#include <set>
#include <limits>
#include <cmath>
#include <tuple>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

// -------------------------------------- セグメントツリー ----------------------------------
class BIT {
public:
	int size_ = 1;
	vector<int> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos & -pos);
		}
	}
	int sum(int pos) {
		pos++; int s = 0;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos & -pos);
		}
		return s;
	}
};

// ------------------------------------- ハッシュ関連の関数 ---------------------------------
long long BASE = 11111111111111LL;
long long power[1 << 18];
long long hush[1 << 18];

void init() {
	power[0] = 1;
	for (int i = 1; i <= 250000; i++) power[i] = BASE * power[i - 1];
}

// -------------------------------------- 幾何関連の関数 ------------------------------------
struct Point {
	long long px, py;
};

long long dst(Point a1, Point a2) {
	return abs(a1.px - a2.px) + abs(a1.py - a2.py);
}

vector<Point> fixes(vector<Point> G) {
	vector<Point> G2;
	for (int i = 0; i < G.size(); i++) {
		int pre = (i + G.size() - 1) % G.size(), nex = (i + 1) % G.size();
		bool s1 = false; if (G[pre].px == G[i].px) s1 = true;
		bool s2 = false; if (G[i].px == G[nex].px) s2 = true;
		if (s1 != s2) G2.push_back(G[i]);
	}
	return G2;
}

long long getmin(vector<long long> t) {
	hush[0] = 1;
	for (int i = 1; i <= t.size() * 2; i++) hush[i] = BASE * hush[i - 1] + t[(i - 1) % t.size()];

	long long minv = 9223372036854775807LL;
	for (int i = 0; i < t.size(); i++) {
		long long val = hush[t.size() + i] - hush[i] * power[t.size()];
		minv = min(minv, val);
	}
	return minv;
}

long long hashval(vector<Point> v) {
	vector<long long> t;
	for (int i = 0; i < v.size(); i++) {
		t.push_back(dst(v[i], v[(i + 1) % v.size()]));
	}
	long long p1 = getmin(t); reverse(t.begin(), t.end());
	long long p2 = getmin(t);
	return min(p1, p2);
}

bool identical(vector<Point> v1, vector<Point> v2) {
	v1 = fixes(v1);
	v2 = fixes(v2);
	if (v1.size() != v2.size()) return false;
	long long val1 = hashval(v1);
	long long val2 = hashval(v2);
	if (val1 == val2) return true;
	return false;
}

// ---------------------------------- 本質 ------------------------------------
long long N, L[1 << 18];
Point Z[1 << 18];

bool dir[1 << 18];
vector<pair<long long, int>> V[1 << 18][2];

vector<tuple<long long, int, int>> T[1 << 18][2];
set<tuple<long long, int, int>> Set;
int GL[1 << 18], GR[1 << 18];

// ---------------------------- その他のライブラリ ---------------------------
bool Rotate(int p1, int p2) {
	if (p1 > p2) p2 += N;
	if (p2 - p1 == 1) return true;
	return false;
}

long long getlen(int p1, int p2) {
	// p1 -> p2 の距離
	if (p1 > p2) p2 += N;
	return L[p2] - L[p1];
}

void adds(vector<Point>& a1, int cl, int cr) {
	if (cl > cr) cr += N;
	for (int i = cl; i <= cr; i++) {
		if (a1[a1.size() - 1].px == Z[i % N].px && a1[a1.size() - 1].py == Z[i % N].py) continue;
		a1.push_back(Z[i % N]);
	}
}

vector<Point> solve() {
	// ステップ A. 座標圧縮をする
	vector<long long> X, Y;
	for (int i = 0; i < N; i++) X.push_back(Z[i].px);
	for (int i = 0; i < N; i++) Y.push_back(Z[i].py);
	sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());

	// ステップ B. 初期化をする
	for (int i = 0; i <= N; i++) {
		V[i][0].clear();
		V[i][1].clear();
	}
	for (int i = 0; i <= N * 2; i++) {
		T[i][0].clear();
		T[i][1].clear();
	}

	// ステップ C. BIT で向きを求める（false: 左側、true: 右側）
	for (int i = 0; i < N; i++) {
		if (Z[i].px == Z[(i + 1) % N].px) continue;
		int pos1 = lower_bound(X.begin(), X.end(), Z[(i + 0) % N].px) - X.begin();
		int pos2 = lower_bound(X.begin(), X.end(), Z[(i + 1) % N].px) - X.begin();
		if (pos1 > pos2) swap(pos1, pos2);
		V[pos1][0].push_back(make_pair(Z[(i + 0) % N].py, i));
		V[pos2][1].push_back(make_pair(Z[(i + 0) % N].py, i));
	}
	BIT ZZ; ZZ.init(Y.size() + 2);
	for (int i = 0; i < X.size(); i++) {
		sort(V[i][0].begin(), V[i][0].end());
		for (pair<long long, int> j : V[i][1]) {
			int pos1 = lower_bound(Y.begin(), Y.end(), j.first) - Y.begin();
			ZZ.add(pos1, -1);
		}
		for (pair<long long, int> j : V[i][0]) {
			int pos1 = lower_bound(Y.begin(), Y.end(), j.first) - Y.begin();
			ZZ.add(pos1, 1);
			if (ZZ.sum(pos1) % 2 == 0) dir[j.second] = true;
			else dir[j.second] = false;
		}
	}

	// ステップ D. 境界値も含め、どこで push するか vector (T) に突っ込む
	for (int i = 0; i < N; i++) {
		if (Z[i].px == Z[(i + 1) % N].px) continue;
		int pos1 = lower_bound(X.begin(), X.end(), Z[(i + 0) % N].px) - X.begin();
		int pos2 = lower_bound(X.begin(), X.end(), Z[(i + 1) % N].px) - X.begin();
		int s0 = (i + N - 1) % N, s1 = (i + 0) % N, s2 = (i + 1) % N, s3 = (i + 2) % N;
		if (pos1 > pos2) { swap(pos1, pos2); swap(s1, s2); swap(s0, s3); }

		if (dir[i] == false) {
			int cl = pos1 * 2, cr = pos2 * 2;
			if (Z[s0].py > Z[s1].py) cl++;
			if (Z[s2].py > Z[s3].py) cr++;
			T[cl][0].push_back(make_tuple(Z[i].py, s1, s2));
			T[cr][1].push_back(make_tuple(Z[i].py, s1, s2));
			GL[i] = cl; GR[i] = cr;
		}
		else {
			int cl = pos1 * 2, cr = pos2 * 2;
			if (Z[s0].py < Z[s1].py) cl++;
			if (Z[s2].py < Z[s3].py) cr++;
			T[cl][0].push_back(make_tuple(Z[i].py, s1, s2));
			T[cr][1].push_back(make_tuple(Z[i].py, s1, s2));
			GL[i] = cl; GR[i] = cr;
		}
	}

	// ステップ E. 平面走査をする
	for (int i = 0; i <= (X.size() - 1) * 2; i++) {
		vector<tuple<long long, int, int>> Important;
		for (tuple<long long, int, int> j : T[i][1]) {
			auto itr = Set.lower_bound(j);
			if (itr != Set.begin()) { itr--; Important.push_back(*itr); itr++; }
			itr++; if (itr != Set.end()) { Important.push_back(*itr); }
			Set.erase(j);
		}
		for (tuple<long long, int, int> j : T[i][0]) {
			Important.push_back(j);
			Set.insert(j);
			auto itr = Set.lower_bound(j);
			if (itr != Set.begin()) { itr--; Important.push_back(*itr); itr++; }
			itr++; if (itr != Set.end()) { Important.push_back(*itr); }
		}

		for(tuple<long long, int, int> j : Important) {
			auto itr = Set.lower_bound(j);
			if (itr == Set.end() || (*itr) != j) continue;
			int num = get<1>(j); if (Rotate(get<1>(j), get<2>(j)) == false) num = get<2>(j);
			if (dir[num] == true) itr--;

			tuple<long long, int, int> fl = (*itr); itr++;
			tuple<long long, int, int> fr = (*itr); itr++;
			long long L1 = 0;
			if (Rotate(get<1>(fl), get<2>(fl)) == true) L1 = getlen(get<1>(fr), get<1>(fl));
			if (Rotate(get<1>(fl), get<2>(fl)) == false) L1 = getlen(get<1>(fl), get<1>(fr));

			int numl = get<1>(fl); if (Rotate(get<1>(fl), get<2>(fl)) == false) numl = get<2>(fl);
			int numr = get<1>(fr); if (Rotate(get<1>(fr), get<2>(fr)) == false) numr = get<2>(fr);
			long long v1l; if (GL[numl] % 2 == 0) v1l = X[GL[numl] / 2]; else v1l = X[GL[numl] / 2] + 1;
			long long v1r; if (GR[numl] % 2 == 0) v1r = X[GR[numl] / 2]; else v1r = X[(GR[numl] + 1) / 2] - 1;
			long long v2l; if (GL[numr] % 2 == 0) v2l = X[GL[numr] / 2]; else v2l = X[GL[numr] / 2] + 1;
			long long v2r; if (GR[numr] % 2 == 0) v2r = X[GR[numr] / 2]; else v2r = X[(GR[numr] + 1) / 2] - 1;

			long long vl = max(v1l, v2l);
			long long vr = min(v1r, v2r);
			long long sl = L1 + abs(Z[get<1>(fl)].px - vl) + abs(Z[get<1>(fr)].px - vl);
			long long sr = L1 + abs(Z[get<1>(fl)].px - vr) + abs(Z[get<1>(fr)].px - vr);
			if (sl <= L[N] / 2LL && L[N] / 2LL <= sr && ((L[N] / 2LL) - sl) % 2LL == 0LL) {
				long long zahyou = vl + ((L[N] / 2LL) - sl) / 2LL;
				vector<Point> D1, D2;
				if (Rotate(get<1>(fl), get<2>(fl)) == true) {
					long long yl_val = get<0>(fl);
					long long yr_val = get<0>(fr);
					D1.push_back(Point{ zahyou, yr_val });
					adds(D1, get<1>(fr), get<1>(fl));
					if (D1[D1.size() - 1].px != zahyou || D1[D1.size() - 1].py != yl_val) D1.push_back({ zahyou, yl_val });
					D2.push_back(Point{ zahyou, yl_val });
					adds(D2, get<2>(fl), get<2>(fr));
					if (D2[D2.size() - 1].px != zahyou || D2[D2.size() - 1].py != yr_val) D2.push_back({ zahyou, yr_val });
				}
				if (Rotate(get<1>(fl), get<2>(fl)) == false) {
					long long yl_val = get<0>(fl);
					long long yr_val = get<0>(fr);
					D1.push_back(Point{ zahyou, yl_val });
					adds(D1, get<1>(fl), get<1>(fr));
					if (D1[D1.size() - 1].px != zahyou || D1[D1.size() - 1].py != yr_val) D1.push_back({ zahyou, yr_val });
					D2.push_back(Point{ zahyou, yr_val });
					adds(D2, get<2>(fr), get<2>(fl));
					if (D2[D2.size() - 1].px != zahyou || D2[D2.size() - 1].py != yl_val) D2.push_back({ zahyou, yl_val });
				}
				bool flag = identical(D1, D2);
				if (flag == true) {
					return vector<Point>{Point{ zahyou, get<0>(fl) }, Point{ zahyou, get<0>(fr) }};
				}
			}
		}
	}

	return vector<Point>{};
}

int main() {
	// ステップ 1. 入力・前準備
	scanf("%lld", &N); init();
	for (int i = 0; i < N; i++) scanf("%lld%lld", &Z[i].px, &Z[i].py);
	for (int i = 0; i < N * 2; i++) L[i + 1] = dst(Z[i % N], Z[(i + 1) % N]);
	for (int i = 1; i <= N * 2; i++) L[i] += L[i - 1];

	// ステップ 2. x 側を探索
	vector<Point> E1 = solve();
	if (E1.size() >= 1) {
		cout << E1[0].px << " " << E1[0].py << " " << E1[1].px << " " << E1[1].py << endl;
		return 0;
	}

	// ステップ 3. y 側を探索
	for (int i = 0; i < N; i++) swap(Z[i].px, Z[i].py);
	vector<Point> E2 = solve();
	if (E2.size() >= 1) {
		cout << E2[0].py << " " << E2[0].px << " " << E2[1].py << " " << E2[1].px << endl;
		return 0;
	}

	cout << "NO" << endl;
	return 0;
}

Compilation message (stderr)

demarcation.cpp:9:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
demarcation.cpp: In function 'std::vector<Point> fixes(std::vector<Point>)':
demarcation.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp: In function 'long long int getmin(std::vector<long long int>)':
demarcation.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= t.size() * 2; i++) hush[i] = BASE * hush[i - 1] + t[(i - 1) % t.size()];
                  ~~^~~~~~~~~~~~~~~
demarcation.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp: In function 'long long int hashval(std::vector<Point>)':
demarcation.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp: In function 'std::vector<Point> solve()':
demarcation.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp:201:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= (X.size() - 1) * 2; i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'int main()':
demarcation.cpp:276:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N); init();
  ~~~~~^~~~~~~~~~~~
demarcation.cpp:277:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%lld%lld", &Z[i].px, &Z[i].py);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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