Submission #711225

#	Time	Username	Problem	Language	Result	Execution time	Memory
711225		EthanKim8683	Walk (CEOI06_walk)	C++17	80 / 100	85 ms	14980 KiB

walk

#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const I X=1e6;
const I Y=1e6;
const Lli MAX=1e18;
tuple<I,I,I,I>rcts[N];
vector<pair<I,I>>ques;
map<I,I>curs;
pair<Lli,I>trns[2][1+2*N];
pair<I,I>pnts[2][1+2*N];
vector<pair<I,I>>ress;
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I x,y;cin>>x>>y;
  I n;cin>>n;
  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};
  }
  tuple<Lli,I,I>res={MAX,-1,-1};
  if(x!=0){
    I low=-Y,upp=Y;
    for(I i=0;i<n;i++){
      auto[x1,y1,x2,y2]=rcts[i];
      if(x>0){
        pnts[0][i*2+1]={x1-1,y1-1};
        pnts[0][i*2+2]={x1-1,y2+1};
        if(x1<x)ques.push_back({-(x1-1),i});
      }
      if(x<0){
        pnts[0][i*2+1]={x2+1,y1-1};
        pnts[0][i*2+2]={x2+1,y2+1};
        if(x2>x)ques.push_back({x2+1,i});
      }
      if(x1<=x&&x<=x2){
        if(y1>y)upp=min(upp,y1-1);
        if(y2<y)low=max(low,y2+1);
      }
    }
    sort(ques.begin(),ques.end());
    fill_n(trns[0],1+2*n,pair<Lli,I>{MAX,-1});
    trns[0][0]={0,0};
    curs.insert({0,0});
    while(ques.size()){
      auto[t,i]=ques.back();ques.pop_back(),t=-t;
      auto[x1,y1,x2,y2]=rcts[i];
      auto low=curs.lower_bound(y1-1);
      auto upp=curs.upper_bound(y2+1);
      I k=i*2+1,l=i*2+2;
      for(auto it=low;it!=upp;it=curs.erase(it)){
        auto[y3,j]=*it;I x3=pnts[0][j].first;
        Lli dis=trns[0][j].first+abs(x3-t);
        trns[0][k]=min(trns[0][k],{abs(y3-(y1-1))+dis,j});
        trns[0][l]=min(trns[0][l],{abs(y3-(y2+1))+dis,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){
      I x1=pnts[0][i].first;
      Lli dis=trns[0][i].first+abs(x-x1)+abs(y-y1);
      res=min(res,{dis,0,i});
    }
    curs.clear();
  }
  if(y!=0){
    I low=-X,upp=X;
    for(I i=0;i<n;i++){
      auto[x1,y1,x2,y2]=rcts[i];
      if(y>0){
        pnts[1][i*2+1]={x1-1,y1-1};
        pnts[1][i*2+2]={x2+1,y1-1};
        if(y1<y)ques.push_back({-(y1-1),i});
      }
      if(y<0){
        pnts[1][i*2+1]={x1-1,y2+1};
        pnts[1][i*2+2]={x2+1,y2+1};
        if(y2>y)ques.push_back({y2+1,i});
      }
      if(y1<=y&&y<=y2){
        if(x1>x)upp=min(upp,x1-1);
        if(x2<x)low=max(low,x2+1);
      }
    }
    sort(ques.begin(),ques.end());
    fill_n(trns[1],1+2*n,pair<Lli,I>{MAX,-1});
    trns[1][0]={0,0};
    curs.insert({0,0});
    while(ques.size()){
      auto[t,i]=ques.back();ques.pop_back(),t=-t;
      auto[x1,y1,x2,y2]=rcts[i];
      auto low=curs.lower_bound(x1-1);
      auto upp=curs.upper_bound(x2+1);
      I k=i*2+1,l=i*2+2;
      for(auto it=low;it!=upp;it=curs.erase(it)){
        auto[x3,j]=*it;I y3=pnts[1][j].second;
        Lli dis=trns[1][j].first+abs(y3-t);
        trns[1][k]=min(trns[1][k],{abs(x3-(x1-1))+dis,j});
        trns[1][l]=min(trns[1][l],{abs(x3-(x2+1))+dis,j});
      }
      if(trns[1][k].first!=MAX)curs.insert({x1-1,k});
      if(trns[1][l].first!=MAX)curs.insert({x2+1,l});
    }
    for(auto[x1,i]:curs)if(low<=x1&&x1<=upp){
      I y1=pnts[1][i].second;
      Lli dis=trns[1][i].first+abs(x-x1)+abs(y-y1);
      res=min(res,{dis,1,i});
    }
    curs.clear();
  }
  auto[dis,t,i]=res;
  if(t==0){
    I x1=x,y1=y;
    while(i!=0){
      auto[x2,y2]=pnts[0][i];
      if(y1!=y2)ress.push_back({0,y1-y2});
      if(x1!=x2)ress.push_back({x1-x2,0});
      x1=x2,y1=y2,i=trns[0][i].second;
    }
    if(y1!=0)ress.push_back({0,y1-0});
    if(x1!=0)ress.push_back({x1-0,0});
  }
  if(t==1){
    I x1=x,y1=y;
    while(i!=0){
      auto[x2,y2]=pnts[1][i];
      if(x1!=x2)ress.push_back({x1-x2,0});
      if(y1!=y2)ress.push_back({0,y1-y2});
      x1=x2,y1=y2,i=trns[1][i].second;
    }
    if(x1!=0)ress.push_back({x1-0,0});
    if(y1!=0)ress.push_back({0,y1-0});
  }
  reverse(ress.begin(),ress.end());
  printf("%lli\n",dis);
  printf("%i\n",ress.size());
  for(auto[x,y]:ress)printf("%i %i\n",x,y);
}

Compilation message (stderr)

walk.cpp: In function 'I main()':
walk.cpp:141: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=]
  141 |   printf("%i\n",ress.size());
      |           ~^    ~~~~~~~~~~~
      |            |             |
      |            int           std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |           %li

• Subtask 1: 80 / 100