제출 #231187

#제출 시각아이디문제언어결과실행 시간메모리
231187thebes전차 (CEOI13_tram)C++14
100 / 100
71 ms6252 KiB
#include <bits/stdc++.h> #define DEBUG 1 using namespace std; namespace output{ void __(short x){cout<<x;} void __(unsigned x){cout<<x;} void __(int x){cout<<x;} void __(long long x){cout<<x;} void __(unsigned long long x){cout<<x;} void __(double x){cout<<x;} void __(long double x){cout<<x;} void __(char x){cout<<x;} void __(const char*x){cout<<x;} void __(const string&x){cout<<x;} void __(bool x){cout<<(x?"true":"false");} template<class S,class T> void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");} template<class T> void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class S,class T> void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} void pr(){cout<<"\n";} template<class S,class... T> void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);} } using namespace output; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,char> pic; typedef pair<double,double> pdd; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vl; #define pb push_back #define fox(i,x,y) for(int i=(x);i<=(y);i++) #define foxr(i,x,y) for(int i=(y);i>=(x);i--) #define F first #define S second const int MN = 2e5+5; int N, M, i, x, y; char ch; pii pos[MN]; double _; struct cmp{bool operator()(const pair<double,ll>&i,const pair<double,ll>&j){return i.F==j.F?i.S<j.S:i.F>j.F;}}; set<pair<double,ll>,cmp> seg; map<ll,ll> st; map<ll,double> dist; inline double dis(pll i,pll j){return sqrt((i.F-j.F)*(i.F-j.F)+(i.S-j.S)*(i.S-j.S));} inline void go(pll &old,double &cur,pll nw,ll x,ll y,ll m1,ll m2){ double mindist=1e9; for(int i=0;i<2;i++){ if((1<<i)&m1) mindist=min(mindist,dis(nw,make_pair(x,i+1))); if((1<<i)&m2) mindist=min(mindist,dis(nw,make_pair(y,i+1))); } if(mindist>cur){ cur=mindist; old=nw; } } inline pll opt(ll x,ll y,ll m1,ll m2){ assert(y>=1); ll mid=(x+y)>>1; double d=0; mid=max(mid,1LL); mid=min(mid,(ll)N); pll ret(mid,1); go(ret,d,make_pair(mid,1),x,y,m1,m2); go(ret,d,make_pair(mid,2),x,y,m1,m2); if(mid+1<=min(y,(ll)N)){ go(ret,d,make_pair(mid+1,1),x,y,m1,m2); go(ret,d,make_pair(mid+1,2),x,y,m1,m2); } _ = d; return ret; } int main(){ scanf("%d%d",&N,&M); st[1-3*N]=st[1+3*N]=3; pll tmp=opt(1-3*N,1+3*N,3,3); dist[1-3*N]=_; seg.insert({_,1-3*N}); for(i=1;i<=M;i++){ /*for(auto v : seg) printf("(%lf, %lld) ",v.F,v.S); pr();*/ scanf(" %c",&ch); if(ch=='E'){ ll lef=seg.begin()->S; auto rit = st.upper_bound(lef); pos[i]=opt(lef,rit->F,st[lef],rit->S); seg.erase(seg.begin()); int flag=0; if(st[pos[i].F]) flag=1; st[pos[i].F]|=(1<<(pos[i].S-1)); auto it = st.lower_bound(pos[i].F); it--; rit = st.upper_bound(pos[i].F); if(flag){ seg.erase({dist[it->F],it->F}); seg.erase({dist[pos[i].F],pos[i].F}); } opt(it->F,pos[i].F,it->S,st[pos[i].F]); dist[it->F]=_; seg.insert({_,it->F}); opt(pos[i].F,rit->F,st[pos[i].F],rit->S); dist[pos[i].F]=_; seg.insert({_,pos[i].F}); printf("%d %d\n",pos[i].F,pos[i].S); } else{ scanf("%d",&x); pll cur=pos[x]; auto lef=st.lower_bound(cur.F); lef--; auto rit=st.upper_bound(cur.F); seg.erase({dist[lef->F],lef->F}); seg.erase({dist[cur.F],cur.F}); st[cur.F]^=(1<<(cur.S-1)); if(!st[cur.F]){ st.erase(cur.F); opt(lef->F,rit->F,lef->S,rit->S); dist[lef->F]=_; seg.insert({_,lef->F}); } else{ opt(lef->F,cur.F,lef->S,st[cur.F]); dist[lef->F]=_; seg.insert({_,lef->F}); opt(cur.F,rit->F,st[cur.F],rit->S); dist[cur.F]=_; seg.insert({_,cur.F}); } } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

tram.cpp: In function 'int main()':
tram.cpp:88:9: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
   88 |     pll tmp=opt(1-3*N,1+3*N,3,3);
      |         ^~~
tram.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
tram.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf(" %c",&ch);
      |         ~~~~~^~~~~~~~~~~
tram.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
#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...