| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 128658 |
2019-07-11T08:10:47 Z |
임유진(#3161) |
None (JOI16_ho_t4) |
C++14 |
|
21 ms |
21368 KB |
#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;
/*
bool cmp(lint a, lint b) {
lint x = B * a.fi - A * a.se - (B * b.fi - A * b.se);
return x != 0 ? x < 0 : (A * a.fi + B * a.se) % ABs < (A * b.fi + B * b.se) % 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);
//printf("[%s]", 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--;
//printf("*%c*", S[i]);
}
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]));
/*
printf("cell: ");
for(auto a : cell) printf("(%lld, %lld) ", a.fi, a.se);
printf("\n");
*/
A = dot[N].fi;
B = dot[N].se;
ABs = A * A + B * B;
//printf("A = %lld, B = %lld\n", A, 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());
//printf("%lu", cell.size());
//for(auto a : cell) printf("(%lld, %lld)\n", a.fi, a.se);
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());
/*
printf("ty: ");
for(auto a : ty) printf("(%lld, %lld)", a.fi, a.se);
printf("\n");
*/
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());
/*
printf("ds[%d]: ", i);
for(auto a : ds[i]) printf("%lld ", a);
printf("\n");
*/
}
for(auto a : cell) ty2.push_back(f(a));
sort(ty2.begin(), ty2.end());
ty2.resize(unique(ty2.begin(), ty2.end()) - ty2.begin());
/*
printf("ty2: ");
for(auto a : ty2) printf("(%lld, %lld)", a.fi, a.se);
printf("\n");
*/
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; } );
/*
printf("cs[%d]: ", i);
for(auto a : cs[i]) printf("(%lld, %lld) ", a.fi, a.se);
printf("\n");
*/
cs[i].resize(unique(cs[i].begin(), cs[i].end()) - cs[i].begin());
/*
printf("cs[%d]: ", i);
for(auto a : cs[i]) printf("(%lld, %lld) ", a.fi, a.se);
printf("\n");
*/
}
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;
}
//printf("x = %lld, y = %lld, ApB = %lld, ds[l][ll - 1] = %lld\n", x, y, ApB, ds[l][ll - 1]);
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]);
ans += (j == 0 ? K : min(done[i][j - 1] + apbdis(cs[i][j - 1], cs[i][j]), (lint) K)) - done[i][j];
//printf("done[%d][%d] = %lld, ans = %lld, (%lld, %lld)\n", i, j, done[i][j], ans, cs[i][j].fi, cs[i][j].se);
}
printf("%lld", ans);
return 0;
}
Compilation message
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:99:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ty.size(); i++) {
~~^~~~~~~~~~~
2016_ho_t4.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ty2.size(); i++) {
~~^~~~~~~~~~~~
2016_ho_t4.cpp:136: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:136: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:142:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(l == ty.size() || ty[l] != f(nd)) {
~~^~~~~~~~~~~~
2016_ho_t4.cpp:43: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
21368 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
21368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
21368 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
21368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
21368 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
21368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
21368 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
21368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
