| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125531 |
2019-07-05T17:10:18 Z |
Retro3014 |
None (JOI16_ho_t4) |
C++17 |
|
2 ms |
376 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int N, K;
string str;
vector<pii> vt;
map<pii, vector<int> > mp;
vector<pii> mrg;
vector<int> tmp;
vector<pii> mrg2;
vector<pii> mrg3;
ll ans;
void merge(){
//cout<<"****************"<<endl;
mrg2.clear();
for(int i=0; i<tmp.size(); i++){
mrg2.pb({tmp[i], tmp[i] + K-1});
//cout<<tmp[i]<<" "<<tmp[i]+K-1<<endl;
}
if(mrg.empty() || mrg2.empty()){
mrg.clear(); return;
}
//cout<<"========="<<endl;
//for(int i=0; i<mrg.size(); i++){
// cout<<mrg[i].first<<" "<<mrg[i].second<<endl;
//}
//cout<<"========="<<endl;
int t1 = mrg[0].first; int t2 = mrg2[0].first;
int n1 = 0, n2 = 0;
int i1=0, i2=0;
int cnt1=0, cnt2=0;
int now = -INF, prv=-1;
while(1){
//cout<<"n "<<t1<<" "<<t2<<endl;
if(t1<t2 || (t1==t2 && n1==0)){
now = max(now, t1);
if(n1!=1){
cnt1++;
t1 = mrg[i1].second;
n1 = 1;
}else{
n1 = 0;
cnt1--;
i1++;
if(i1>=mrg.size()){
if(prv!=-1){
mrg3.pb({prv, now});
}
break;
}
t1 = mrg[i1].first;
}
}else{
now = max(now, t2);
if(n2!=1){
cnt2++;
while(i2+1<mrg2.size() && mrg2[i2+1].first<=mrg2[i2].second){
i2++;
}
t2 = mrg2[i2].second;
n2 = 1;
}else{
n2 = 0;
cnt2--;
i2++;
if(i2>=mrg2.size()){
if(prv!=-1){
mrg3.pb({prv, now});
}
break;
}
t2 = mrg2[i2].first;
}
}
if(cnt1>0 && cnt2>0){
if(prv==-1){
prv = now;
}
}else{
if(prv!=-1){
mrg3.pb({prv, now});
prv = -1;
}
}
}
mrg = mrg3;
mrg3.clear();
//for(int i=0; i<mrg.size(); i++){
//cout<<mrg[i].first<<" "<<mrg[i].second<<endl;
//}
return;
}
int main(){
scanf("%d%d", &N, &K);
cin>>str;
int x = 0, y = 0;
for(int i=1; i<=N+1; i++){
vt.pb({x, y});
if(i==N+1) break;
if(str[i-1]=='N'){
y++;
}else if(str[i-1]=='E'){
x++;
}else if(str[i-1]=='W'){
x--;
}else{
y--;
}
}
if(x==0){
int tmp = x; x = y; y = tmp;
for(int i=0; i<vt.size(); i++){
tmp = vt[i].first; vt[i].first = vt[i].second; vt[i].second = tmp;
}
}
//cout<<x<<" "<<y<<endl;
for(int i=0; i<vt.size(); i++){
int t;
if(x==0){
t = 0;
}else if(x<0){
if(vt[i].first==0){
t = 0;
}
else if(vt[i].first>0){
t = vt[i].first / x;
}else{
t = vt[i].first / x + (((vt[i].first/x) * x ==vt[i].first)?0:1);
}
}else{
if(vt[i].first==0){
t = 0;
}else if(vt[i].first>0){
t = vt[i].first/x;
}else{
t = vt[i].first / x - (((vt[i].first/x) * x ==vt[i].first)?0:1);
}
}
vt[i].first -= x * t;
vt[i].second -= y * t;
//cout<<"a "<<vt[i].first<<" "<<vt[i].second<<" "<<t<<endl;
mp[vt[i]].pb(t);
if(vt[i].first==0){
if(x==0) continue;
if(x>0){
vt[i].first+=x; vt[i].second+=y;
//cout<<"a "<<vt[i].first<<" "<<vt[i].second<<" "<<t-1<<endl;
mp[vt[i]].pb(t-1);
}else{
vt[i].first-=x; vt[i].second-=y;
//cout<<"a "<<vt[i].first<<" "<<vt[i].second<<" "<<t+1<<endl;
mp[vt[i]].pb(t+1);
}
}
}
//cout<<"**"<<endl;
for(map<pii, vector<int> >::iterator it = mp.begin(); it!=mp.end(); it++){
tmp = it->second;
sort(tmp.begin(), tmp.end());
mp[it->first] = tmp;
}
for(map<pii, vector<int> >::iterator it = mp.begin(); it!=mp.end(); it++){
pii p = it->first;
//if(p.first==x) continue;
//cout<<"+"<<p.first<<" "<<p.second<<endl;
//if(x==0){
if(mp.find({(p.first+1), p.second})==mp.end() || mp.find({p.first, p.second+1})==mp.end() || mp.find({(p.first+1), p.second+1})==mp.end()) continue;
mrg.clear(); mrg2.clear();
mrg.pb({0, INF}); tmp = mp[p]; merge();
tmp = mp[{p.first+1, p.second}]; merge();
tmp = mp[{p.first, p.second+1}]; merge();
tmp = mp[{p.first+1, p.second+1}]; merge();
for(int i=0; i<mrg.size(); i++){
ans += mrg[i].second - mrg[i].first + 1;
//cout<<'*'<<mrg[i].first<<" "<<mrg[i].second<<endl;
}
/*}else{
if(mp.find({p.first+1, p.second})==mp.end() || mp.find({p.first, p.second+1})==mp.end() || mp.find({p.first+1, p.second+1})==mp.end()) continue;
mrg.clear(); mrg2.clear();
mrg.pb({1, K}); tmp = mp[p]; merge();
tmp = mp[{(p.first+1)%x, p.second}]; merge();
tmp = mp[{p.first, p.second+1}]; merge();
tmp = mp[{(p.first+1)%x, p.second+1}]; merge();
for(int i=0; i<mrg.size(); i++){
ans += mrg[i].second - mrg[i].first;
cout<<'*'<<mrg[i].first<<" "<<mrg[i].second<<endl;
}
}*/
}
cout<<ans;
return 0;
}
Compilation message
2016_ho_t4.cpp: In function 'void merge()':
2016_ho_t4.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<tmp.size(); i++){
~^~~~~~~~~~~
2016_ho_t4.cpp:71:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1>=mrg.size()){
~~^~~~~~~~~~~~
2016_ho_t4.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i2+1<mrg2.size() && mrg2[i2+1].first<=mrg2[i2].second){
~~~~^~~~~~~~~~~~
2016_ho_t4.cpp:92:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i2>=mrg2.size()){
~~^~~~~~~~~~~~~
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:139:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<vt.size(); i++){
~^~~~~~~~~~
2016_ho_t4.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<vt.size(); i++){
~^~~~~~~~~~
2016_ho_t4.cpp:200:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<mrg.size(); i++){
~^~~~~~~~~~~
2016_ho_t4.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &K);
~~~~~^~~~~~~~~~~~~~~~
| # |
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 |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
