Submission #245127

#TimeUsernameProblemLanguageResultExecution timeMemory
245127TadijaSebezTram (CEOI13_tram)C++11
100 / 100
151 ms9964 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> const int N=150050; int dist[N][2]; bool active[N][2],has[N][2]; set<pair<int,pii>> pos; void Cons(int x,int y,vector<int> pts){ if(active[x][y])return; int dst=N*2; for(int i:pts){ for(int j=0;j<2;j++){ if(has[i][j]){ dst=min(dst,x!=i?abs(x-i)*2+abs(y-j):abs(y-j)*2); //printf("(%i %i - %i) ",i,j,x!=i?abs(x-i)*2+abs(y-j):abs(y-j)*2); } } } dist[x][y]=dst; active[x][y]=1; //printf("Add %i %i %i : ",x,y,dst);for(int i:pts)printf("%i ",i);printf("\n"); pos.insert({-dst,{x,y}}); } void Del(int x,int y){ if(active[x][y]){ //printf("Del %i %i %i\n",x,y,dist[x][y]); pos.erase({-dist[x][y],{x,y}}); active[x][y]=0; } } int X[N],Y[N],n,m; set<int> idx; void Rec(set<int>::iterator it,int mod){ vector<int> cns,tke; if(it==idx.end()&&it==idx.begin()){ cns={1};tke={}; }else if(it==idx.end()){ cns={n};tke={*prev(it)}; }else if(it==idx.begin()){ cns={1};tke={*it}; }else{ int mid=*it+*prev(it)>>1; if((*it+*prev(it))&1)cns={mid,mid+1}; else cns={mid}; tke={*it,*prev(it)}; } if(mod==0||mod==2){ for(int i:cns)Del(i,0),Del(i,1); } if(mod==1||mod==2){ for(int i:cns)Cons(i,0,tke),Cons(i,1,tke); } } int main(){ scanf("%i %i",&n,&m); Rec(idx.begin(),1); for(int i=1;i<=m;i++){ char c;scanf("\n%c",&c); if(c=='E'){ tie(X[i],Y[i])=pos.begin()->second; //cout<<pos.begin()->first<<" "<<pos.begin()->second.first<<" "<<pos.begin()->second.second<<"\n"; printf("%i %i\n",X[i],Y[i]+1); Del(X[i],Y[i]); has[X[i]][Y[i]]=1; if(idx.count(X[i])){ Rec(idx.find(X[i]),2); Rec(next(idx.find(X[i])),2); }else{ Rec(idx.upper_bound(X[i]),0); idx.insert(X[i]); Rec(idx.find(X[i]),1); Rec(next(idx.find(X[i])),1); } }else{ int p;scanf("%i",&p); has[X[p]][Y[p]]=0; if(!has[X[p]][Y[p]^1]){ Rec(idx.find(X[p]),0); Rec(next(idx.find(X[p])),0); idx.erase(X[p]); auto it=idx.upper_bound(X[p]); Rec(it,1); if(it!=idx.begin())Rec(prev(it),2); if(it!=idx.end())Rec(next(it),2); }else{ Rec(idx.find(X[p]),2); Rec(next(idx.find(X[p])),2); } } } return 0; }

Compilation message (stderr)

tram.cpp: In function 'void Rec(std::set<int>::iterator, int)':
tram.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=*it+*prev(it)>>1;
      |           ~~~^~~~~~~~~~
tram.cpp: In function 'int main()':
tram.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
tram.cpp:58:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   char c;scanf("\n%c",&c);
      |          ~~~~~^~~~~~~~~~~
tram.cpp:75:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |    int p;scanf("%i",&p);
      |          ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...