| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130116 |
2019-07-14T03:13:12 Z |
EntityIT |
None (JOI16_ho_t4) |
C++14 |
|
2 ms |
376 KB |
#include<bits/stdc++.h>
using namespace std;
#define int ll
using ll = long long;
const ll infll = (ll)1e18 + 123;
int n, K, dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }, dir[200], a, b;
ll ans;
string s;
struct Type {
ll r_x, r_y, q_f, q_l;
Type (ll _r_x = 0, ll _r_y = 0, ll _q_f = 0, ll _q_l = 0) : r_x(_r_x), r_y(_r_y), q_f(_q_f), q_l(_q_l) {}
bool operator< (const Type &_) const { return array<ll, 4>{ r_x, r_y, q_f, q_l } < array<ll, 4>{ _.r_x, _.r_y, _.q_f, _.q_l }; }
};
vector<Type> type, _type;
ll get_frst (ll r_x, ll r_y) {
if (r_x == a) {
r_x -= a;
r_y -= b;
}
int pos = (int)(lower_bound(type.begin(), type.end(), Type(r_x, r_y, -infll, -infll) ) - type.begin() );
if (pos == (int)type.size() || array<ll, 2>{ r_x, r_y } != array<ll, 2>{ type[pos].r_x, type[pos].r_y } ) return infll;
else return type[pos].q_f;
}
ll get_lst (ll r_x, ll r_y) {
if (r_x == a) {
r_x -= a;
r_y -= b;
}
int pos = (int)(lower_bound(type.begin(), type.end(), Type(r_x, r_y, -infll, -infll) ) - type.begin() );
if (pos == (int)type.size() || array<ll, 2>{ r_x, r_y } != array<ll, 2>{ type[pos].r_x, type[pos].r_y } ) return -infll;
else return type[pos].q_l;
}
void specCase () {
set< array<ll, 2> > set_;
for (int x = 0, y = 0, i = -1; i < n; ++i) {
if (i >= 0) x += dx[ dir[ s[i] - 'A' ] ], y += dy[ dir[ s[i] - 'A' ] ];
set_.insert(array<ll, 2>{ x, y } );
}
for (auto _ : set_) {
ans += (set_.find(array<ll, 2>{ _[0] + 1, _[1] + 1 } ) != set_.end() &&
set_.find(array<ll, 2>{ _[0], _[1] + 1 } ) != set_.end() &&
set_.find(array<ll, 2>{ _[0] + 1, _[1] } ) != set_.end() );
}
cout << ans;
}
int32_t main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("test.INP", "r", stdin);
//// freopen("Seeht.OUT", "w", stdout);
cin >> n >> K >> s;
dir['E' - 'A'] = 2;
dir['N' - 'A'] = 1;
dir['W' - 'A'] = 0;
dir['S' - 'A'] = 3;
for (int i = 0; i < n; ++i) a += dx[ dir[ s[i] - 'A' ] ], b += dy[ dir[ s[i] - 'A' ] ];
// cout << "a = " << a << " b = " << b << '\n';
if (a < 0) {
a = -a;
for (int i = 0; i < n; ++i) {
if (s[i] == 'E') s[i] = 'W';
else if (s[i] == 'W') s[i] = 'E';
}
}
if (b < 0) {
b = -b;
for (int i = 0; i < n; ++i) {
if (s[i] == 'N') s[i] = 'S';
else if (s[i] == 'S') s[i] = 'N';
}
}
if (!a && !b) {
specCase();
return 0;
}
if (!a) {
swap(a, b);
for (int i = 0; i < n; ++i) {
if (s[i] == 'E') s[i] = 'N';
else if (s[i] == 'N') s[i] = 'E';
else if (s[i] == 'W') s[i] = 'S';
else if (s[i] == 'S') s[i] = 'W';
}
}
for (int x = 0, y = 0, i = -1; i < n; ++i) {
if (i >= 0) x += dx[ dir[ s[i] - 'A' ] ], y += dy[ dir[ s[i] - 'A' ] ];
ll r_x, r_y, q_f, q_l;
r_x = x % a;
if (r_x < 0) r_x += a;
q_f = (-r_x + x) / a;
r_y = -(int)q_f * b + y;
q_l = q_f + K - 1;
type.push_back(Type(r_x, r_y, q_f, q_l) );
}
sort(type.begin(), type.end() );
for (int i = 0; i < (int)type.size(); ++i) {
for (int _i = i + 1; _i <= (int)type.size(); ++_i) {
if (_i == (int)type.size() || array<ll, 2>{ type[i].r_x, type[i].r_y } != array<ll, 2>{ type[_i].r_x, type[_i].r_y }) {
_type.push_back(Type(type[i].r_x, type[i].r_y, type[i].q_f, type[_i - 1].q_l) );
i = _i - 1;
break ;
}
}
}
type = _type;
for (int i = 0; i < (int)type.size(); ++i) {
ll frst = type[i].q_f, lst = type[i].q_l;
frst = max(frst, get_frst(type[i].r_x + 1, type[i].r_y + 1) - (type[i].r_x + 1 == a) );
lst = min(lst, get_lst(type[i].r_x + 1, type[i].r_y + 1) - (type[i].r_x + 1 == a) );
frst = max(frst, get_frst(type[i].r_x, type[i].r_y + 1) );
lst = min(lst, get_lst(type[i].r_x, type[i].r_y + 1) );
frst = max(frst, get_frst(type[i].r_x + 1, type[i].r_y) - (type[i].r_x + 1 == a) );
lst = min(lst, get_lst(type[i].r_x + 1, type[i].r_y) - (type[i].r_x + 1 == a) );
ans += max(0LL, lst - frst + 1);
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
