Submission #853653

#	Time	Username	Problem	Language	Result	Execution time	Memory
853653		idiotcomputer	Walk (CEOI06_walk)	C++11	100 / 100	81 ms	10964 KiB

walk

#include <bits/stdc++.h>
using namespace std;

struct point {
    int x,y,idx,pos;
};

struct rect {
    int x1,y1,x2,y2;
    int n1 = -1;
    int n2 = -1;
    long long int s1 = (long long int) 1e15;
    long long int s2 = (long long int) 1e15;
    int b1 = -1;
    int b2 = -1;
};

bool comp(point &a, point &b){
    if (a.x == b.x){
        if (a.y == b.y){
            return a.pos < b.pos;
        }
        return a.y > b.y;
    }
    return a.x < b.x;
}

int dist(int x1, int y1, int x2, int y2){
    return abs(x1-x2) + abs(y1-y2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x,y;
    cin >> x >> y;
    int n;
    cin >> n;
    
    vector<point> points;
    vector<rect> rects;
    rect temp;
    point t2;
    int cnt = 0;
    for (int i =0; i < n; i++){
        cin >> temp.x1 >> temp.y1 >> temp.x2 >> temp.y2;
        if (temp.x1 >= x){
            continue;
        }
        temp.x2 = min(temp.x2,x-1);
        rects.push_back(temp);
        points.push_back(t2);
        points.push_back(t2);
        points[2*cnt].x = temp.x1-1;
        points[2*cnt].y = temp.y1-1;
        points[2*cnt].idx = cnt;
        points[2*cnt].pos = 0;
        
        points[2*cnt+1].x = temp.x2+1;
        points[2*cnt+1].y = temp.y2+1;
        points[2*cnt+1].idx = cnt;
        points[2*cnt+1].pos = 1;
        cnt++;
    }
    temp.x1 = x;
    temp.x2 = x;
    temp.y1 = y;
    temp.y2 = y;
    rects.push_back(temp);
    points.push_back(t2);
    points.push_back(t2);
    n = (int) rects.size();

    points[2*n-2].x = temp.x1;
    points[2*n-2].y = temp.y1;
    points[2*n-2].idx = (int) (rects.size())-1;
    points[2*n-2].pos = 0;
        
    points[2*n-1].x = temp.x2;
    points[2*n-1].y = temp.y2;
    points[2*n-1].idx = (int) (rects.size())-1;
    points[2*n-1].pos = 1;
    
    
    sort(points.begin(),points.end(),comp);
    set<pair<int,int>> all;
    for (int i =2*n-1; i >= 0; i--){
        if (points[i].pos == 1){
            auto it = all.lower_bound({rects[points[i].idx].y1,-1});
            while (it != all.end() && (*it).first <= (points[i].y)-1){
                if (points[(*it).second].pos == 0){
                    rects[points[(*it).second].idx].n1 = points[i].idx;
                } else {
                    rects[points[(*it).second].idx].n2 = points[i].idx;
                }
                auto it2 = it;
                it++;
                all.erase(it2);
            }
        }
        all.insert({points[i].y,i});
    }
  
    int next;
    int cidx;
    int v1,v2;
    for (int i =0; i < 2*n; i++){
        cidx = points[i].idx;
        if (points[i].pos == 0){
            next = rects[cidx].n1;
        } else {
            next = rects[cidx].n2;
        }
        if (next == -1){
            if (points[i].pos == 0){
                rects[cidx].s1 = dist(0,0,points[i].x,points[i].y);
            } else {
                rects[cidx].s2 = dist(0,0,points[i].x,points[i].y);
            }
            continue;
        }
        if (points[i].pos == 0){
            v1 = rects[next].s1+dist(points[i].x,points[i].y,rects[next].x1-1,rects[next].y1-1);
            v2 = rects[next].s2+dist(points[i].x,points[i].y,rects[next].x2+1,rects[next].y2+1);
            rects[cidx].s1 = min(v1,v2);
            if (v1 < v2){
                rects[cidx].b1 = 0;
            } else {
                rects[cidx].b1 = 1;
            }
        } else {
            v1 = rects[next].s1+dist(points[i].x,points[i].y,rects[next].x1-1,rects[next].y1-1);
            v2 = rects[next].s2+dist(points[i].x,points[i].y,rects[next].x2+1,rects[next].y2+1);
            rects[cidx].s2 = min(v1,v2);
            if (v1 < v2){
                rects[cidx].b2 = 0;
            } else {
                rects[cidx].b2 = 1;
            }
        }
    }
    
    pair<int,int> rt;
    vector<pair<int,int>> res;
    int curr = n-1;
    int cp = 0;
    int cx,cy,ty,tx;
    int wp;
    rects[n-1].x1 += 1;
    rects[n-1].y1 += 1;
    while (true){
        if (cp == 0){
            cx = rects[curr].x1-1;
            cy = rects[curr].y1-1;
            next = rects[curr].n1;
            wp = rects[curr].b1;
        } else {
            cx = rects[curr].x2+1;
            cy = rects[curr].y2+1;
            next = rects[curr].n2;
            wp = rects[curr].b2;
        }
        if (next == -1){
            tx = 0;
            ty = 0;
        } else {
            tx = rects[next].x2+1;
            if (wp == 0){
                ty = rects[next].y1-1;
            } else {
                ty = rects[next].y2+1;
            }
        }
        rt.first = tx - cx;
        rt.second = 0;
        res.push_back(rt);
        rt.first = 0;
        rt.second = ty - cy;
        res.push_back(rt);
        if (wp == 0){
            rt.first = rects[next].x1-1 - tx;
            rt.second = 0;
            res.push_back(rt);
        }
        if (next == -1){
            break;
        }
        curr = next;
        cp = wp;
    }
    
    wp = -1;
    cx = 0;
    cy = 0;
    
    vector<pair<int,int>> fin;
    for (int i =res.size()-1; i >= 0; i--){
        if (res[i].first == 0){
            if (wp == 1 || wp ==-1){
                cy -= res[i].second;
                wp = 1;
            } else{
                fin.push_back({cx,cy});
                cx = 0;
                cy = -1 * res[i].second;
                wp = 1;
            }
        } else {
             if (wp == 0 || wp ==-1){
                cx -= res[i].first;
                wp = 0;
            } else{
                fin.push_back({cx,cy});
                cx = -1 * res[i].first;
                cy = 0;
                wp = 0;
            }
        }
    }
    if (wp != -1){
        fin.push_back({cx,cy});
    }
    cout << rects[n-1].s1 << "\n";
    cout << fin.size() << '\n';
    for (int i =0; i < fin.size(); i++){
        cout << fin[i].first << " " << fin[i].second << '\n';
    }
    
    return 0;
}

Compilation message (stderr)

walk.cpp: In function 'int main()':
walk.cpp:226:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |     for (int i =0; i < fin.size(); i++){
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100