| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 711413 |
2023-03-16T21:12:13 Z |
EthanKim8683 |
Walk (CEOI06_walk) |
C++17 |
|
116 ms |
19272 KB |
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const I Y=1e6;
const Lli MAX=1e18;
tuple<I,I,I,I>rcts[N];
vector<pair<I,I>>ques;
pair<I,I>pnts[4*N+2];
map<I,I>curs;
pair<Lli,I>trns[2][4*N+2];
vector<pair<I,I>>ress;
I dis(I a,I b){
auto[x1,y1]=pnts[a];auto[x2,y2]=pnts[b];
return abs(x1-x2)+abs(y1-y2);
}
void mov(I x1,I y1){
if(ress.size()){
auto[x2,y2]=ress.back();
if(x1!=0&&x2!=0)ress.pop_back(),x1+=x2;
if(y1!=0&&y2!=0)ress.pop_back(),y1+=y2;
}
if(x1==0&&y1==0)return;
ress.push_back({x1,y1});
}
I main(){
cin.tie(0)->sync_with_stdio(0);
fill(&trns[0][0],&trns[0][0]+2*(4*N+2),pair<Lli,I>{MAX,-1});
I x,y;cin>>x>>y;
I n;cin>>n;
I c=4*n+0,d=4*n+1;
pnts[c]={0,0},pnts[d]={x,y};
I low=-Y,upp=Y;
for(I i=0;i<n;i++){
I x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
rcts[i]={x1,y1,x2,y2};
I j=4*i+0,k=4*i+1,l=4*i+2,m=4*i+3;
pnts[j]={x1-1,y1-1},pnts[k]={x1-1,y2+1};
pnts[l]={x2+1,y1-1},pnts[m]={x2+1,y2+1};
if(x1<=x&&x<=x2){
if(y1>y)upp=min(upp,y1-1);
if(y2<y)low=max(low,y2+1);
}
}
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
if(x1<x)ques.push_back({-(x1-1),i});
}
sort(ques.begin(),ques.end());
curs.insert({0,c});
trns[0][c]={0,-1};
while(ques.size()){
auto[t,i]=ques.back();ques.pop_back();
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(y1-1);
auto upp=curs.upper_bound(y2+1);
I k=4*i+0,l=4*i+1;
for(auto it=low;it!=upp;it=curs.erase(it)){
auto[y3,j]=*it;
trns[0][k]=min(trns[0][k],{trns[0][j].first+dis(j,k),j});
trns[0][l]=min(trns[0][l],{trns[0][j].first+dis(j,l),j});
}
if(trns[0][k].first!=MAX)curs.insert({y1-1,k});
if(trns[0][l].first!=MAX)curs.insert({y2+1,l});
}
for(auto[y1,i]:curs)if(low<=y1&&y1<=upp){
trns[0][d]=min(trns[0][d],{trns[0][i].first+dis(d,i),i});
}
curs.clear();
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
if(x2<x)ques.push_back({x2+1,i});
}
sort(ques.begin(),ques.end());
curs.insert({y,d});
trns[1][d]={0,-1};
while(ques.size()){
auto[t,i]=ques.back();ques.pop_back();
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(y1-1);
auto upp=curs.upper_bound(y2+1);
I k=4*i+2,l=4*i+3;
for(auto it=low;it!=upp;it=curs.erase(it)){
auto[y3,j]=*it;
trns[1][k]=min(trns[1][k],{trns[1][j].first+dis(j,k),j});
trns[1][l]=min(trns[1][l],{trns[1][j].first+dis(j,l),j});
}
if(trns[1][k].first!=MAX)curs.insert({y1-1,k});
if(trns[1][l].first!=MAX)curs.insert({y2+1,l});
}
for(auto[y1,i]:curs){
trns[1][c]=min(trns[1][c],{trns[1][i].first+dis(c,i),i});
}
for(I i=0;i<n;i++){
I j=4*i+0,k=4*i+1,l=4*i+2,m=4*i+3;
trns[0][l]={trns[0][j].first+dis(l,j),j};
trns[0][m]={trns[0][k].first+dis(m,k),k};
trns[1][j]={trns[1][l].first+dis(j,l),l};
trns[1][k]={trns[1][m].first+dis(k,m),m};
}
pair<Lli,I>res={MAX,-1};
for(I i=0;i<4*n+2;i++){
res=min(res,{trns[0][i].first+trns[1][i].first,i});
}
auto[tot,i]=res;
for(I j=i;j!=c;){
auto[cur,k]=trns[0][j];
auto[x1,y1]=pnts[j];auto[x2,y2]=pnts[k];
mov(0,y1-y2),mov(x1-x2,0),j=k;
}
reverse(ress.begin(),ress.end());
for(I j=i;j!=d;){
auto[cur,k]=trns[1][j];
auto[x1,y1]=pnts[j];auto[x2,y2]=pnts[k];
mov(0,y2-y1),mov(x2-x1,0),j=k;
}
printf("%lli\n",tot);
printf("%i\n",ress.size());
for(auto[x,y]:ress)printf("%i %i\n",x,y);
}
Compilation message
walk.cpp: In function 'I main()':
walk.cpp:121:12: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
121 | printf("%i\n",ress.size());
| ~^ ~~~~~~~~~~~
| | |
| int std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
| %li
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 4 |
Correct |
7 ms |
12840 KB |
Output is correct |
| 5 |
Correct |
79 ms |
18060 KB |
Output is correct |
| 6 |
Correct |
26 ms |
14572 KB |
Output is correct |
| 7 |
Correct |
40 ms |
15860 KB |
Output is correct |
| 8 |
Correct |
61 ms |
18672 KB |
Output is correct |
| 9 |
Correct |
116 ms |
19116 KB |
Output is correct |
| 10 |
Correct |
102 ms |
19272 KB |
Output is correct |
