제출 #624414

#제출 시각아이디문제언어결과실행 시간메모리
624414andrei_boaca전차 (CEOI13_tram)C++14
65 / 100
1096 ms2056 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; ll n,m; bool have[150005][3]; set<ll> s; pii where[30005]; ll dist(ll a, ll b, ll c, ll d) { return (a-c)*(a-c)+(b-d)*(b-d); } int rgt[150005],lft[150005]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; int cur=0; have[0][1]=have[0][2]=1; have[n+1][1]=have[n+1][2]=1; rgt[0]=n+1; while(m--) { cur++; char c; cin>>c; if(c=='E') { /*if(s.empty()) { cout<<1<<' '<<1<<'\n'; s.insert(1); have[1][1]=1; where[cur]={1,1}; continue; }*/ vector<int> v; int poz=0; while(true) { v.push_back(poz); if(poz==n+1) break; poz=rgt[poz]; } ll dmax=0; int mylft,myrgt; pii who; for(int i=1;i<v.size();i++) { int st=v[i-1]; int dr=v[i]; int mij=(st+dr)/2; for(int a=st;a<=st+1;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } if(minim>dmax) { dmax=minim; who={a,j}; mylft=st; myrgt=dr; } } for(int a=mij;a<=mij+1;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } if(minim>dmax) { dmax=minim; who={a,j}; mylft=st; myrgt=dr; } } for(int a=dr-1;a<=dr;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } if(minim>dmax) { dmax=minim; who={a,j}; mylft=st; myrgt=dr; } } } cout<<who.first<<' '<<who.second<<'\n'; have[who.first][who.second]=1; int g=who.first; where[cur]=who; if(have[g][1]+have[g][2]==1) { rgt[mylft]=g; rgt[g]=myrgt; lft[g]=mylft; lft[myrgt]=g; } } else { int p; cin>>p; int lin=where[p].first,col=where[p].second; have[lin][col]=0; if(have[lin][1]+have[lin][2]==0) { int L=lft[lin]; int R=rgt[lin]; rgt[L]=R; lft[R]=L; } } } return 0; }

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

tram.cpp: In function 'int main()':
tram.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
tram.cpp:129:27: warning: 'myrgt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |                 lft[myrgt]=g;
      |                 ~~~~~~~~~~^~
tram.cpp:128:23: warning: 'mylft' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |                 lft[g]=mylft;
      |                 ~~~~~~^~~~~~
#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...