This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
map<pair<int, int>, bool>mp;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
string s;
cin>>n>>k>>s;
assert(k==1 || n<=60);
int x=0, y=0;
mp[{0, 0}]=true;
set<pair<int, int>>v;
v.insert({0, 0});
for(int i=0;i<n;i++){
if(s[i]=='E') x++;
if(s[i]=='W') x--;
if(s[i]=='N') y--;
if(s[i]=='S') y++;
v.insert({x, y});
}
int dy=y, dx=x;
set<pair<int, int>>v2;
int cnt=0;
if(k<=60){
for(int i=0;i<k;i++){
for(auto [x, y]:v){
v2.insert({x+i*dx, y+i*dy});
}
}
for(auto i:v2){
int x=i.first, y=i.second;
if(v2.find({x+1, y})!=v2.end() && v2.find({x, y+1})!=v2.end() && v2.find({x+1, y+1})!=v2.end()){
cnt++;
}
}
}
else{
for(int i=0;i<60;i++){
for(auto [x, y]:v){
v2.insert({x+i*dx, y+i*dy});
}
}
int A=0;
for(auto i:v2){
int x=i.first, y=i.second;
if(v2.find({x+1, y})!=v2.end() && v2.find({x, y+1})!=v2.end() && v2.find({x+1, y+1})!=v2.end()){
A++;
}
}
for(auto [x, y]:v){
v2.insert({x+60*dx, y+60*dy});
}
int B=0;
for(auto i:v2){
int x=i.first, y=i.second;
if(v2.find({x+1, y})!=v2.end() && v2.find({x, y+1})!=v2.end() && v2.find({x+1, y+1})!=v2.end()){
B++;
}
}
B-=A;
cnt=A+B*(k-60);
}
cout<<cnt;
}
Compilation message (stderr)
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:29:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [x, y]:v){
^
2016_ho_t4.cpp:42:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [x, y]:v){
^
2016_ho_t4.cpp:53:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [x, y]:v){
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |