| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594105 |
2022-07-12T06:02:29 Z |
박상훈(#8431) |
None (JOI16_ho_t4) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, k, dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1}, cc[1234];
char s[100100];
map<pair<ll, ll>, vector<pair<ll, ll>>> M;
ll a, b, d, ans;
pair<ll, ll> _convert(ll x, ll y){
return {a*x+b*y, x/(a/d)%d};
}
ll myabs(ll x){
if (x<0) return -x;
return x;
}
ll fx = 0, fy = 0;
void simulate(bool flag){
if (flag) M[_convert(0, 0)].emplace_back(fx, fx+(ll)k*a);
for (int i=1;i<=n;i++){
fx += dx[cc[s[i]]], fy += dy[cc[s[i]]];
if (flag){
auto p = _convert(fx, fy);
M[p].emplace_back(fx, fx + (ll)k*a);
}
}
}
void compress(vector<pair<ll, ll>> &V){
vector<pair<ll, ll>> ret;
sort(V.begin(), V.end());
for (auto &[s, e]:V){
if (ret.empty()) {ret.emplace_back(s, e); continue;}
if (ret.back().second>=s) ret.back().second = e;
else ret.emplace_back(s, e);
}
swap(V, ret);
}
void init(){
cc['E'] = 0, cc['S'] = 1, cc['W'] = 2, cc['N'] = 3;
simulate(0);
if (fx==0 && fy==0) {fx = 1; k = 1;}
else if (fx==0){
cc['E'] = 3, cc['N'] = 0;
cc['S'] = 2, cc['W'] = 1;
fx = 0, fy = 0;
simulate(0);
assert(fx);
}
d = myabs(__gcd(fx, fy));
a = -fy, b = fx;
fx = 0, fy = 0;
//printf(" a = %lld, b = %lld, d = %lld\n", a, b, d);
simulate(1);
for (auto &[p, V]:M) compress(V);
//printf("Init ok\n");
}
void get_event(vector<pair<ll, int>> &Event, vector<pair<ll, ll>> &V, int ofs){
for (auto &[s, e]:V){
Event.emplace_back(s+ofs, 1);
Event.emplace_back(e+ofs, -1);
}
}
bool valid(ll x, ll y){
if (M.find(_convert(x, y+1))==M.end()) return 0;
if (M.find(_convert(x+1, y))==M.end()) return 0;
if (M.find(_convert(x+1, y+1))==M.end()) return 0;
return 1;
}
void solve(){
for (auto &[p, V]:M){
ll x = V[0].first;
ll y = (p.first - x*a) / b;
if (!valid(x, y)) continue;
vector<pair<ll, int>> Event;
get_event(Event, V, 0);
get_event(Event, M[_convert(x, y+1)], 0);
get_event(Event, M[_convert(x+1, y)], -1);
get_event(Event, M[_convert(x+1, y+1)], -1);
sort(Event.begin(), Event.end());
int cnt = 0;
for (int i=0;i<(int)Event.size();){
int r = i;
for (;r<(int)Event.size();r++){
if (Event[i].first!=Event[r].first) break;
cnt += Event[r].second;
}
if (cnt==4){
assert(r<(int)Event.size());
ans += (Event[r].first - Event[i].first) / a;
}
assert(i<r);
i = r;
}
}
}
int main(){
scanf("%d %d", &n, &k);
scanf("%s", s+1);
init();
solve();
printf("%lld\n", ans);
return 0;
}
Compilation message
2016_ho_t4.cpp: In function 'void simulate(bool)':
2016_ho_t4.cpp:25:24: warning: array subscript has type 'char' [-Wchar-subscripts]
25 | fx += dx[cc[s[i]]], fy += dy[cc[s[i]]];
| ~~~^
2016_ho_t4.cpp:25:44: warning: array subscript has type 'char' [-Wchar-subscripts]
25 | fx += dx[cc[s[i]]], fy += dy[cc[s[i]]];
| ~~~^
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
2016_ho_t4.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%s", s+1);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
