Submission #128796

#	Time	Username	Problem	Language	Result	Execution time	Memory
128796		imyujin	영역 (JOI16_ho_t4)	C++14	100 / 100	308 ms	56268 KiB

2016_ho_t4

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 100005
#define fi first
#define se second

typedef long long lint;
typedef pair<lint, lint> pll;

const lint LINF = 1ll << 50;
const int mm[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
char S[MAXN];
vector<pll> dot;
vector<pll> ty, ty2;
vector<lint> ds[MAXN];
vector<pll> cell, cs[4 * MAXN];
vector<lint> done[4 * MAXN];
lint A, B, ABs;

pll f(pll &a) {
	return make_pair(B * a.fi - A * a.se, ((A * a.fi + B * a.se) % ABs + ABs) % ABs);
}

lint apbdis(pll &a, pll &b) {	//a < b
	return (A * (b.fi - a.fi) + B * (b.se - a.se)) / ABs;
}

int main() {
	int N, K;
	lint ans = 0ll;

	scanf("%d%d%s", &N, &K, S);

	dot.push_back(make_pair(0ll, 0ll));
	for(int i = 0; i < N; i++) {
		dot.push_back(dot.back());
		if(S[i] == 'W') dot[i + 1].fi--;
		else if(S[i] == 'E') dot[i + 1].fi++;
		else if(S[i] == 'N') dot[i + 1].se++;
		else dot[i + 1].se--;
	}
	for(int i = 0; i <= N; i++) for(int j = 0; j < 4; j++) 
		cell.push_back(make_pair(dot[i].fi - mm[j][0], dot[i].se - mm[j][1]));

	A = dot[N].fi;
	B = dot[N].se;
	ABs = A * A + B * B;
	if(A == 0 && B == 0) {
		sort(dot.begin(), dot.end());
		dot.resize(unique(dot.begin(), dot.end()) - dot.begin());
		sort(cell.begin(), cell.end());
		cell.resize(unique(cell.begin(), cell.end()) - cell.begin());

		int ans = 0;
		for(auto &a : cell) {
			bool b = true;
			for(int j = 0; j < 4; j++) b &= binary_search(dot.begin(), dot.end(), make_pair(a.fi + mm[j][0], a.se + mm[j][1]));
			if(b) ans++;
		}
		printf("%d", ans);
		return 0;
	}

	for(auto &a : dot) ty.push_back(f(a));
	sort(ty.begin(), ty.end());
	ty.resize(unique(ty.begin(), ty.end()) - ty.begin());
	for(auto &a : dot) {
		int l = lower_bound(ty.begin(), ty.end(), f(a)) - ty.begin();
		ds[l].push_back(A * a.fi + B * a.se);
	}
	for(int i = 0; i < ty.size(); i++) {
		sort(ds[i].begin(), ds[i].end());
		ds[i].resize(unique(ds[i].begin(), ds[i].end()) - ds[i].begin());
	}

	for(auto &a : cell) ty2.push_back(f(a));
	sort(ty2.begin(), ty2.end());
	ty2.resize(unique(ty2.begin(), ty2.end()) - ty2.begin());
	for(auto &a : cell) {
		int l = lower_bound(ty2.begin(), ty2.end(), f(a)) - ty2.begin();
		cs[l].push_back(a);
	}
	for(int i = 0; i < ty2.size(); i++) {
		sort(cs[i].begin(), cs[i].end(), [&](pll a, pll b) { return A * a.fi + B * a.se < A * b.fi + B * b.se; } );
		cs[i].resize(unique(cs[i].begin(), cs[i].end()) - cs[i].begin());
	}

	for(int i = 0; i < ty2.size(); i++) for(int j = 0; j < cs[i].size(); j++) {
		done[i].push_back(0ll);
		for(int k = 0; k < 4; k++) {
			lint x = cs[i][j].fi + mm[k][0], y = cs[i][j].se + mm[k][1];
			pll nd = make_pair(x, y);
			int l = lower_bound(ty.begin(), ty.end(), f(nd)) - ty.begin();
			if(l == ty.size() || ty[l] != f(nd)) {
				done[i][j] = K;
				break;
			}
			lint ApB = A * x + B * y;
			int ll = upper_bound(ds[l].begin(), ds[l].end(), ApB) - ds[l].begin();
			if(ll == 0) {
				done[i][j] = K;
				break;
			}
			done[i][j] = max(done[i][j], (ApB - ds[l][ll - 1]) / ABs);
		}
		if(j > 0) done[i][j] = min(done[i][j - 1] + apbdis(cs[i][j - 1], cs[i][j]), done[i][j]);
		done[i][j] = min(done[i][j], (lint) K);
		ans += (j == 0 ? K : min(done[i][j - 1] + apbdis(cs[i][j - 1], cs[i][j]), (lint) K)) - done[i][j];
	}

	printf("%lld", ans);

	return 0;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ty.size(); i++) {
                 ~~^~~~~~~~~~~
2016_ho_t4.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ty2.size(); i++) {
                 ~~^~~~~~~~~~~~
2016_ho_t4.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ty2.size(); i++) for(int j = 0; j < cs[i].size(); j++) {
                 ~~^~~~~~~~~~~~
2016_ho_t4.cpp:92:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ty2.size(); i++) for(int j = 0; j < cs[i].size(); j++) {
                                                     ~~^~~~~~~~~~~~~~
2016_ho_t4.cpp:98:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(l == ty.size() || ty[l] != f(nd)) {
       ~~^~~~~~~~~~~~
2016_ho_t4.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%s", &N, &K, S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~

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