Submission #732807

#	Time	Username	Problem	Language	Result	Execution time	Memory
732807		flappybird	영역 (JOI16_ho_t4)	C++17	100 / 100	554 ms	38152 KiB

2016_ho_t4

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
pii arr[MAX];
int fdiv(int x, int y) {
	if (!y) return 0;
	if (x % y == 0) return x / y;
	if (x < 0) return x / y - 1;
	return x / y;
}
int fmod(int x, int y) {
	if (!y) return x;
	x %= y;
	x += y;
	x %= y;
	return x;
}
bool valid(vector<pii>& v, pii p) {
	int ind = lower_bound(v.begin(), v.end(), p) - v.begin();
	if (ind >= v.size()) return false;
	return v[ind] == p;
}
bool exist(set<pii>& st, pii p) {
	return st.find(p) != st.end();
}
int chkv[3][3];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	cin >> N >> K;
	int i;
	string s;
	cin >> s;
	for (i = 1; i <= N; i++) {
		arr[i] = arr[i - 1];
		if (s[i - 1] == 'N') arr[i].first++;
		if (s[i - 1] == 'S') arr[i].first--;
		if (s[i - 1] == 'E') arr[i].second++;
		if (s[i - 1] == 'W') arr[i].second--;
	}
	if (arr[N].first > 0) for (i = 1; i <= N; i++) arr[i].first *= -1;
	if (arr[N].second > 0) for (i = 1; i <= N; i++) arr[i].second *= -1;
	vector<pii> v;
	set<pii> real;
	for (i = 1; i <= N; i++) real.insert(arr[i]);
	int X, Y;
	X = -arr[N].first;
	Y = -arr[N].second;
	if (!X && !Y) K = 1;
	if (K == 1) {
		for (i = 0; i <= N; i++) {
			int a, b;
			for (a = arr[i].first - 1; a <= arr[i].first + 1; a++) for (b = arr[i].second - 1; b <= arr[i].second + 1; b++) v.emplace_back(a, b);
		}
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		int ans = 0;
		real.emplace(0, 0);
		for (auto& [x, y] : v) {
			if (exist(real, pii(x, y)) && exist(real, pii(x, y + 1)) && exist(real, pii(x + 1, y)) && exist(real, pii(x + 1, y + 1))) ans++;
		}
		cout << ans << ln;
		return 0;
	}
	for (i = 1; i <= N; i++) {
		int a, b;
		for (a = arr[i].first - 1; a <= arr[i].first + 1; a++) for (b = arr[i].second - 1; b <= arr[i].second + 1; b++) v.emplace_back(a, b);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	map<tuple<int, int, int>, int> chk;
	map<pii, int> mp;
	for (auto& [x, y] : v) {
		auto t = make_tuple(fmod(x, X), fmod(y, Y), fdiv(x, X) - fdiv(y, Y));
		if (!X) t = make_tuple(fmod(x, X), fmod(y, Y), 0);
		if (!Y) t = make_tuple(fmod(x, X), fmod(y, Y), 0);
		int res = -1;
		int v;
		if (!Y) v = fdiv(x, X);
		else v = fdiv(y, Y);
		if (chk.find(t) != chk.end()) res = v - chk[t];
		mp[pii(x, y)] = res;
		if (exist(real, pii(x, y))) chk[t] = v;
	}
	ll ans = 0;
	for (auto& [x, y] : v) {
		int mx0, mx1;
		mx0 = mx1 = -1;
		int c = 1;
		int cnt = 0;
		int r = 0;
		for (auto xx : { x, x + 1 }) {
			for (auto yy : { y, y + 1 }) {
				if (real.find(pii(xx, yy)) != real.end()) {
					cnt++;
					if (!~mp[pii(xx, yy)]) r = 1;
					mx1 = max(mx1, mp[pii(xx, yy)]);
				}
				else {
					if (!~mp[pii(xx, yy)]) {
						c = 0;
						break;
					}
					mx0 = max(mx0, mp[pii(xx, yy)]);
				}
				if (!valid(v, pii(xx, yy))) {
					c = 0;
					break;
				}
			}
			if (!c) break;
		}
		if (!c) continue;
		if (!cnt) continue;
		if (cnt == 4) mx0 = 0;
		if (r) mx1 = K;
		if (!~mx0 && cnt < 4) continue;
		mx1 = min(K, mx1);
		ans += max(0, mx1 - mx0);
	}
	auto findmin = [&](int x, int y) {
		int mn = K;
		for (int t = 1; t <= N; t++) {
			int dx = arr[t].first - x;
			int dy = arr[t].second - y;
			if (!X && dx) continue;
			if (!Y && dy) continue;
			if ((!X || dx % X == 0) && (!Y || dy % Y == 0)) {
				int t1, t2;
				t1 = t2 = -1;
				if (dx < 0 || dy < 0) continue;
				if (X) t1 = dx / X;
				if (Y) t2 = dy / Y;
				if (!~t1) t1 = t2;
				if (!~t2) t2 = t1;
				if (t1 == t2) mn = min(mn, t1);
			}
		}
		return mn;
	};
	int j;
	if (findmin(0, 0) >= K) {
		for (i = -1; i <= 1; i++) for (j = -1; j <= 1; j++) {
			chkv[i + 1][j + 1] = findmin(i, j);
		}
		if (chkv[0][0] < K && chkv[0][1] < K && chkv[1][0] < K) ans++;
		if (chkv[1][0] < K && chkv[2][0] < K && chkv[2][1] < K) ans++;
		if (chkv[0][1] < K && chkv[0][2] < K && chkv[1][2] < K) ans++;
		if (chkv[2][2] < K && chkv[2][1] < K && chkv[1][2] < K) ans++;
	}
	cout << ans << ln;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'bool valid(std::vector<std::pair<int, int> >&, pii)':
2016_ho_t4.cpp:32:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  if (ind >= v.size()) return false;
      |      ~~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 62 / 62