Submission #6366390
Source Code Expand
#include<bits/stdc++.h> using namespace std; 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; vector< array<ll, 4> > vecAns; 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 }; } bool operator> (const Type &_) const { return _ < *this; } bool operator== (const Type &_) const { return !(*this < _ || _ < *this); } }; vector<Type> type; void get (ll r_x, ll r_y, int _1, int _2) { int tmp = 0; if (r_x == a) { tmp = 1; r_x -= a; r_y -= b; } int pos = (int)(lower_bound(type.begin(), type.end(), Type(r_x, r_y, -infll, -infll) ) - type.begin() ); for (; pos < (int)type.size() && array<ll, 2>{ r_x, r_y } == array<ll, 2>{ type[pos].r_x, type[pos].r_y }; ++pos) { vecAns.push_back(array<ll, 4>{ type[pos].q_f - tmp, _1, _2, 1 } ); vecAns.push_back(array<ll, 4>{ type[pos].q_l + 1 - tmp, _1, _2, -1 } ); } } 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); 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' ] ]; 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() ); type.erase(unique(type.begin(), type.end() ), type.end() ); for (int i = 0; i < (int)type.size(); ++i) { vecAns.clear(); get(type[i].r_x, type[i].r_y, 0, 0); get(type[i].r_x, type[i].r_y + 1, 0, 1); get(type[i].r_x + 1, type[i].r_y, 1, 0); get(type[i].r_x + 1, type[i].r_y + 1, 1, 1); int cnt[2][2], Cnt = 0; memset(cnt, 0, sizeof cnt); sort(vecAns.begin(), vecAns.end() ); ll lst = -infll; for (auto _ : vecAns) { if (!cnt[ _[1] ][ _[2] ] && _[3] == 1) { if (Cnt == 3) lst = _[0]; ++Cnt; } if (cnt[ _[1] ][ _[2] ] == 1 && _[3] == -1) { if (Cnt == 4) ans += _[0] - lst; --Cnt; } cnt[ _[1] ][ _[2] ] += (int)_[3]; } for (int j = i + 1; j <= (int)type.size(); ++j) { if (j == (int)type.size() ) { i = j - 1; break ; } if (array<ll, 2>{ type[i].r_x, type[i].r_y } != array<ll, 2>{ type[j].r_x, type[j].r_y } ) { i = j - 1; break ; } } } cout << ans << '\n'; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 縄張り (Territory) |
User | EntityIT |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 4458 Byte |
Status | WA |
Exec Time | 185 ms |
Memory | 14652 KB |
Judge Result
Set Name | Subtask01 | Subtask02 | Subtask03 | Subtask04 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 5 | 0 / 10 | 0 / 23 | 0 / 62 | ||||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Subtask01 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, sample-01.txt, sample-03.txt |
Subtask02 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, sample-01.txt, sample-03.txt |
Subtask03 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask04 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 04-08.txt, 04-09.txt, 04-10.txt, 04-11.txt, 04-12.txt, 04-13.txt, 04-14.txt, 04-15.txt, 04-16.txt, 04-17.txt, 04-18.txt, 04-19.txt, 04-20.txt, 04-21.txt, 04-22.txt, 04-23.txt, 04-24.txt, 04-25.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | WA | 1 ms | 256 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | AC | 1 ms | 256 KB |
01-06.txt | AC | 1 ms | 256 KB |
01-07.txt | AC | 1 ms | 256 KB |
01-08.txt | AC | 1 ms | 256 KB |
01-09.txt | AC | 1 ms | 256 KB |
01-10.txt | AC | 1 ms | 256 KB |
01-11.txt | AC | 1 ms | 256 KB |
01-12.txt | AC | 1 ms | 256 KB |
01-13.txt | WA | 1 ms | 256 KB |
01-14.txt | AC | 1 ms | 256 KB |
01-15.txt | AC | 1 ms | 256 KB |
01-16.txt | AC | 1 ms | 256 KB |
01-17.txt | AC | 1 ms | 256 KB |
01-18.txt | AC | 1 ms | 256 KB |
01-19.txt | AC | 1 ms | 256 KB |
01-20.txt | WA | 1 ms | 256 KB |
01-21.txt | AC | 1 ms | 256 KB |
01-22.txt | AC | 1 ms | 256 KB |
01-23.txt | AC | 1 ms | 256 KB |
01-24.txt | WA | 1 ms | 256 KB |
01-25.txt | AC | 1 ms | 256 KB |
02-01.txt | AC | 1 ms | 256 KB |
02-02.txt | AC | 3 ms | 640 KB |
02-03.txt | WA | 4 ms | 512 KB |
02-04.txt | AC | 20 ms | 2548 KB |
02-05.txt | AC | 27 ms | 5488 KB |
02-06.txt | AC | 73 ms | 5696 KB |
02-07.txt | WA | 19 ms | 1616 KB |
02-08.txt | AC | 41 ms | 6592 KB |
02-09.txt | AC | 41 ms | 4672 KB |
02-10.txt | AC | 39 ms | 4672 KB |
02-11.txt | AC | 37 ms | 6080 KB |
02-12.txt | WA | 21 ms | 1872 KB |
02-13.txt | AC | 39 ms | 6336 KB |
02-14.txt | AC | 40 ms | 5312 KB |
02-15.txt | WA | 19 ms | 1616 KB |
02-16.txt | AC | 38 ms | 4800 KB |
02-17.txt | AC | 33 ms | 5312 KB |
02-18.txt | AC | 40 ms | 5952 KB |
02-19.txt | AC | 37 ms | 5568 KB |
02-20.txt | AC | 36 ms | 5184 KB |
02-21.txt | AC | 58 ms | 5568 KB |
02-22.txt | AC | 74 ms | 6336 KB |
02-23.txt | AC | 185 ms | 14396 KB |
02-24.txt | AC | 90 ms | 6080 KB |
02-25.txt | AC | 90 ms | 5824 KB |
03-01.txt | AC | 1 ms | 256 KB |
03-02.txt | WA | 1 ms | 256 KB |
03-03.txt | AC | 1 ms | 256 KB |
03-04.txt | AC | 1 ms | 256 KB |
03-05.txt | AC | 1 ms | 256 KB |
03-06.txt | AC | 1 ms | 256 KB |
03-07.txt | AC | 1 ms | 256 KB |
03-08.txt | AC | 1 ms | 256 KB |
03-09.txt | AC | 1 ms | 256 KB |
03-10.txt | AC | 1 ms | 256 KB |
03-11.txt | AC | 1 ms | 256 KB |
03-12.txt | AC | 1 ms | 256 KB |
03-13.txt | AC | 1 ms | 256 KB |
03-14.txt | AC | 1 ms | 256 KB |
03-15.txt | WA | 1 ms | 256 KB |
03-16.txt | AC | 1 ms | 256 KB |
03-17.txt | WA | 1 ms | 256 KB |
03-18.txt | AC | 1 ms | 256 KB |
03-19.txt | AC | 1 ms | 256 KB |
03-20.txt | AC | 1 ms | 256 KB |
03-21.txt | AC | 1 ms | 256 KB |
03-22.txt | AC | 1 ms | 256 KB |
03-23.txt | AC | 1 ms | 256 KB |
03-24.txt | AC | 1 ms | 256 KB |
03-25.txt | AC | 1 ms | 256 KB |
04-01.txt | AC | 4 ms | 640 KB |
04-02.txt | WA | 3 ms | 384 KB |
04-03.txt | AC | 18 ms | 1792 KB |
04-04.txt | AC | 40 ms | 2548 KB |
04-05.txt | AC | 31 ms | 6384 KB |
04-06.txt | WA | 21 ms | 1900 KB |
04-07.txt | AC | 38 ms | 5696 KB |
04-08.txt | AC | 34 ms | 6208 KB |
04-09.txt | AC | 39 ms | 6208 KB |
04-10.txt | AC | 39 ms | 4928 KB |
04-11.txt | AC | 94 ms | 9916 KB |
04-12.txt | AC | 42 ms | 5184 KB |
04-13.txt | AC | 38 ms | 5184 KB |
04-14.txt | AC | 39 ms | 5184 KB |
04-15.txt | WA | 21 ms | 1872 KB |
04-16.txt | AC | 39 ms | 5312 KB |
04-17.txt | AC | 40 ms | 5696 KB |
04-18.txt | AC | 39 ms | 4672 KB |
04-19.txt | AC | 35 ms | 5056 KB |
04-20.txt | AC | 35 ms | 5952 KB |
04-21.txt | AC | 58 ms | 4672 KB |
04-22.txt | AC | 73 ms | 6080 KB |
04-23.txt | AC | 86 ms | 14652 KB |
04-24.txt | AC | 90 ms | 5312 KB |
04-25.txt | AC | 109 ms | 5184 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 1 ms | 256 KB |
sample-04.txt | AC | 1 ms | 256 KB |