| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 128603 |
2019-07-11T07:20:26 Z |
구재현(#3166) |
None (JOI16_ho_t4) |
C++14 |
|
2 ms |
504 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
using lint = long long;
using pi = pair<lint, lint>;
int n, k;
char str[MAXN];
vector<pi> canon(vector<pi> v){
vector<pi> ev;
for(auto &i : v){
ev.emplace_back(i.first, +1);
ev.emplace_back(i.second + 1, -1);
}
sort(ev.begin(), ev.end());
vector<pi> ret;
int cnt = 0;
for(int i=0; i+1<ev.size(); i++){
cnt += ev[i].second;
if(ev[i].first != ev[i + 1].first){
if(cnt > 0){
ret.emplace_back(ev[i].first, ev[i + 1].first);
}
}
}
return ret;
}
lint getInsecLength(vector<pi> a, vector<pi> b, vector<pi> c, vector<pi> d){
vector<pi> ev;
for(auto &i : a){
ev.emplace_back(i.first, +1);
ev.emplace_back(i.second, -1);
}
for(auto &i : b){
ev.emplace_back(i.first, +1);
ev.emplace_back(i.second, -1);
}
for(auto &i : c){
ev.emplace_back(i.first, +1);
ev.emplace_back(i.second, -1);
}
for(auto &i : d){
ev.emplace_back(i.first, +1);
ev.emplace_back(i.second, -1);
}
sort(ev.begin(), ev.end());
int cnt = 0; lint ret = 0;
for(int i=0; i+1<ev.size(); i++){
cnt += ev[i].second;
if(ev[i].first != ev[i + 1].first){
if(cnt == 4){
ret += ev[i + 1].first - ev[i].first;
}
}
}
return ret;
}
int main(){
scanf("%d %d",&n,&k);
scanf("%s", str);
vector<pi> v = {pi(0, 0)};
lint px = 0, py = 0;
for(int j=0; j<n; j++){
if(str[j] == 'E') px++;
if(str[j] == 'W') px--;
if(str[j] == 'N') py++;
if(str[j] == 'S') py--;
v.emplace_back(px, py);
}
if(v.back().first < 0){
for(auto &i : v) i.first *= -1;
}
if(v.back().second < 0){
for(auto &i : v) i.second *= -1;
}
if(v.back().first == 0){
for(auto &i : v) swap(i.first, i.second);
}
if(v.back() == pi(0, 0)) k = 1;
pi vect = v.back();
v.pop_back();
map<pi, vector<pi>> mp;
for(int i=0; i<v.size(); i++){
lint px = v[i].first;
lint py = v[i].second;
lint s = 0, e = k - 1;
if(i == 0) e = k;
if(px >= vect.first){
int delta = px / vect.first;
px -= delta * vect.first;
py -= delta * vect.second;
s += delta;
e += delta;
}
if(px < 0){
int delta = (vect.first - px - 1) / vect.first;
px += delta * vect.first;
py += delta * vect.second;
s -= delta;
e -= delta;
}
assert(px >= 0 && px < vect.first);
// printf("event %lld %lld = [%lld, %lld]\n", px, py, s, e);
mp[pi(px, py)].emplace_back(s, e);
}
for(auto &i : mp){
i.second = canon(i.second);
}
lint ret = 0;
for(auto &i : mp){
lint x, y; tie(x, y) = i.first;
auto n2 = pi(x, y + 1);
auto n3 = pi(x + 1, y);
auto n4 = pi(x + 1, y + 1);
if(x + 1 == vect.first){
n3.first -= vect.first;
n3.second -= vect.second;
n4.first -= vect.first;
n4.second -= vect.second;
}
if(mp.count(n2) && mp.count(n3) && mp.count(n4)){
auto i1 = i.second;
auto i2 = mp[n2];
auto i3 = mp[n3];
auto i4 = mp[n4];
if(x + 1 == vect.first){
for(auto &x : i3){
x.first--; x.second--;
}
for(auto &x : i4){
x.first--; x.second--;
}
}
ret += getInsecLength(i1, i2, i3, i4);
}
}
cout << ret << endl;
return 0;
}
Compilation message
2016_ho_t4.cpp: In function 'std::vector<std::pair<long long int, long long int> > canon(std::vector<std::pair<long long int, long long int> >)':
2016_ho_t4.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<ev.size(); i++){
~~~^~~~~~~~~~
2016_ho_t4.cpp: In function 'lint getInsecLength(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
2016_ho_t4.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<ev.size(); i++){
~~~^~~~~~~~~~
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
2016_ho_t4.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&k);
~~~~~^~~~~~~~~~~~~~~
2016_ho_t4.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
