Labyrintti

input/code.cpp: In function 'int main()':
input/code.cpp:157:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < corners.size(); i++){
                      ^

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;

class Wall{
public:
    LL start, end;
    bool hori;
    LL pos;
    bool is_null;
    LL id;
};

vector<Wall> walls;

Wall go_left(LL x1, LL y1){
    Wall best; best.is_null = true;
    for(auto wall : walls){
        if(!wall.hori && wall.pos < x1){
            if(y1 >= wall.start && y1 <= wall.end){
                if(best.is_null || wall.pos > best.pos)
                    best = wall;
            }
        }
    }
    return best;
}

Wall go_right(LL x1, LL y1){
    Wall best; best.is_null = true;
    for(auto wall : walls){
        if(!wall.hori && wall.pos > x1){
            if(y1 >= wall.start && y1 <= wall.end){
                if(best.is_null || wall.pos < best.pos)
                    best = wall;
            }
        }
    }
    return best;    
}

Wall go_up(LL x1, LL y1){
    Wall best; best.is_null = true;
    for(auto wall : walls){
        if(wall.hori && wall.pos > y1){
            if(x1 >= wall.start && x1 <= wall.end){
                if(best.is_null || wall.pos < best.pos)
                    best = wall;
            }
        }
    }
    return best;      
}

Wall go_down(LL x1, LL y1){
    Wall best; best.is_null = true;
    for(auto wall : walls){
        if(wall.hori && wall.pos < y1){
            if(x1 >= wall.start && x1 <= wall.end){
                if(best.is_null || wall.pos > best.pos)
                    best = wall;
            }
        }
    }
    return best;          
}


bool can_see(LL x1, LL y1, LL x2, LL y2){
    if(go_left(x1,y1).id == go_left(x2,y2).id && go_right(x1,y1).id == go_right(x2,y2).id) return true;
    if(go_up(x1,y1).id == go_up(x2,y2).id && go_down(x1,y1).id == go_down(x2,y2).id) return true;
    return false;
}

LL manhattan(LL x1, LL y1, LL x2, LL y2){
    return abs(x1-x2) + abs(y1-y2);
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    LL y1,x1,y2,x2;
    cin >> y1 >> x1 >> y2 >> x2;
    y1 = -y1; y2 = -y2;
    
    LL px = 0; LL py = 0;
    LL step = 1;
    vector<pair<LL,LL> > corners;
    vector<LL> corner_distances;
    corners.push_back({-1,1});
    corners.push_back({-1,-1});
    corner_distances.push_back(0);
    corner_distances.push_back(2);
    
    for(int i = 0; i < 1000; i++){
        Wall W;
        
        // Right
        step *= 2;
        W.start = px; px += step; W.end = px;
        W.pos = py;
        W.hori = true;
        W.is_null = false;
        W.id = step;
        walls.push_back(W);
        corners.push_back({corners.back().first + step + 2, corners.back().second});
        corner_distances.push_back(step + 2);
        
        // Up
        step *= 2;
        W.start = py; py += step; W.end = py;
        W.pos = px;
        W.hori = false;
        W.is_null = false;
        W.id = step;
        walls.push_back(W);
        corners.push_back({corners.back().first, corners.back().second + step + 2});
        corner_distances.push_back(step + 2);
        
        // Left
        step *= 2;
        W.end = px; px -= step; W.start = px;
        W.pos = py;
        W.hori = true;
        W.is_null = false;
        W.id = step;
        walls.push_back(W);
        corners.push_back({corners.back().first - step - 2, corners.back().second});
        corner_distances.push_back(step + 2);
        
        // Down
        step *= 2;
        W.end = py; py -= step; W.start = py;
        W.pos = px;
        W.hori = false;
        W.is_null = false;
        W.id = step;
        walls.push_back(W);
        corners.push_back({corners.back().first, corners.back().second - step - 2});
        corner_distances.push_back(step + 2);
        
        if(step >= 1e17) break;

    }

    if(can_see(x1,y1,x2,y2)){
        cout << abs(x1-x2) + abs(y1-y2) << endl;
        return 0;
    }
    
    vector<LL> visible_A, visible_B;
    for(int i = 0; i < corners.size(); i++){
        auto p = corners[i];
        if(can_see(x1,y1,p.first,p.second))
            visible_A.push_back(i);
        if(can_see(x2,y2,p.first,p.second))
            visible_B.push_back(i);
    }
    
    LL ans = 1e18;
    for(auto c1 : visible_A){
        for(auto c2 : visible_B){
            LL d = 0;
            for(int i = min(c1,c2) + 1; i <= max(c1,c2); i++){
                d += corner_distances[i];
            }
            ans = min(ans,d + manhattan(x1,y1,corners[c1].first, corners[c1].second)
                            + manhattan(x2,y2,corners[c2].first, corners[c2].second)
            );
        }
    }
    
    cout << ans << endl;

}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED