// 일단 내보기
// 그 뭐냐 예제 4에서 뒷쪽에 의해 정사각형이 색칠되는게 제대로 고려 안 됨
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#pragma region Geometry
using P = complex<ll>; using ld = long double; using Poly = vector<P>;
const ld PI = acos(-1.0L), TAU = 2*PI;
#define X real()
#define Y imag()
inline ll dot(P u, P v) { return (conj(u)*v).X; }
inline ll cross(P u, P v) { return (conj(u)*v).Y; }
inline ll norm(P u) { return dot(u,u); }
inline int ccw(P a, P b, P c) {
auto v = cross(b-a,c-b);
if (v < 0) return -1;
else if (v > 0) return 1;
return 0;
}
P operator * (const P &lhs, const ll &rhs) { return {lhs.X * rhs, lhs.Y * rhs}; }
inline ld abs(P u) {return sqrt(ld(norm(u)));}
istream &operator >> (istream &is, P &p) {ll x, y; is >> x >> y; p = {x,y}; return is;}
namespace std { bool operator < (const P &u, const P &v) {return u.X == v.X ? u.Y < v.Y : u.X < v.X;} }
#pragma endregion
constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); }
constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); }
const int N = 1e5+3;
int n, k;
P v[N], p[N];
set<P> s;
map<P,vector<ll>> m;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
rep(i,1,n) {
char c; cin >> c;
if (c=='W') v[i]={-1,0};
if (c=='S') v[i]={0,+1};
if (c=='N') v[i]={0,-1};
if (c=='E') v[i]={+1,0};
p[i] = v[i]+p[i-1];
}
ll d = 0;
auto nor = [&](P x) {
d=0;
if (p[n].X) d = floor(x.X,p[n].X);
else if (p[n].Y) d = floor(x.Y,p[n].Y);
return x-p[n]*d;
};
rep(i,0,n) {
P t = nor(p[i]);
m[t].push_back(d);
}
ll ans = 0;
for (auto &[k,v] : m) sort(all(v));
map<P,bool> done;
rep(i,0,n) {
for (auto e : {p[i],p[i]+P{-1,0},p[i]+P{0,-1},p[i]+P{-1,-1}}) {
ll x = e.X, y = e.Y, z = 0;
vector<ll> vec;
if (m.count(nor({x,y}))) {
vec = m[nor({x,y})];
if (!binary_search(all(vec),d)) {
auto it = upper_bound(all(vec),d);
if (it != begin(vec))
Mup(z, 0LL+(d-*prev(it)));
else continue;
}
} else continue;
if (m.count(nor({x+1,y}))) {
vec = m[nor({x+1,y})];
if (!binary_search(all(vec),d)) {
auto it = upper_bound(all(vec),d);
if (it != begin(vec))
Mup(z, 0LL+(d-*prev(it)));
else continue;
}
} else continue;
if (m.count(nor({x,y+1}))) {
vec = m[nor({x,y+1})];
if (!binary_search(all(vec),d)) {
auto it = upper_bound(all(vec),d);
if (it != begin(vec))
Mup(z, 0LL+(d-*prev(it)));
else continue;
}
} else continue;
if (m.count(nor({x+1,y+1}))) {
vec = m[nor({x+1,y+1})];
if (!binary_search(all(vec),d)) {
auto it = upper_bound(all(vec),d);
if (it != begin(vec))
Mup(z, 0LL+(d-*prev(it)));
else continue;
}
} else continue;
if (done[nor({x,y})]) continue;
done[nor({x,y})] = true;
// cout << e << ' ' << nor(e) << ' ' << z << endl;
ans += max(0LL,k-z);
}
}
cout << ans;
}
Compilation message
2016_ho_t4.cpp:15: warning: ignoring '#pragma region Geometry' [-Wunknown-pragmas]
15 | #pragma region Geometry
|
2016_ho_t4.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
33 | #pragma endregion
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2520 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2520 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2520 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2520 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
