CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-10 21:15:44 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED29
#3ACCEPTED59
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.05 s2details
#8ACCEPTED0.05 s2details
#9ACCEPTED0.06 s2details
#10ACCEPTED0.06 s2details
#11ACCEPTED0.05 s3details
#12ACCEPTED0.06 s3details
#13ACCEPTED0.05 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.06 s3details

Compiler report

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++){
                      ^

Code

#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 details

Test 1

Group: 1

Verdict: ACCEPTED

input
6 -1 8 -2

correct output
3

user output
3

Test 2

Group: 1

Verdict: ACCEPTED

input
-8 2 8 -9

correct output
27

user output
27

Test 3

Group: 1

Verdict: ACCEPTED

input
3 2 -5 -1

correct output
13

user output
13

Test 4

Group: 1

Verdict: ACCEPTED

input
4 4 2 7

correct output
5

user output
5

Test 5

Group: 1

Verdict: ACCEPTED

input
-5 4 -6 -3

correct output
8

user output
8

Test 6

Group: 2

Verdict: ACCEPTED

input
-156 226 -9 7

correct output
438

user output
438

Test 7

Group: 2

Verdict: ACCEPTED

input
403 265 10 0

correct output
1100

user output
1100

Test 8

Group: 2

Verdict: ACCEPTED

input
146 462 9 -3

correct output
1160

user output
1160

Test 9

Group: 2

Verdict: ACCEPTED

input
223 82 -1 5

correct output
725

user output
725

Test 10

Group: 2

Verdict: ACCEPTED

input
1 390 -5 2

correct output
436

user output
436

Test 11

Group: 3

Verdict: ACCEPTED

input
-540305713988379 -580514137141...

correct output
1233409841814111

user output
1233409841814111

Test 12

Group: 3

Verdict: ACCEPTED

input
-156703691254895 -816797859965...

correct output
1086091541904259

user output
1086091541904259

Test 13

Group: 3

Verdict: ACCEPTED

input
-438806811971369 -748477242640...

correct output
1299874045296142

user output
1299874045296142

Test 14

Group: 3

Verdict: ACCEPTED

input
939351840049839 -9541207461566...

correct output
2118652567575152

user output
2118652567575152

Test 15

Group: 3

Verdict: ACCEPTED

input
-840127817790022 1113515308437...

correct output
1007774343975947

user output
1007774343975947