CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-10 20:58:47 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.05 s1details
#40.06 s1details
#5ACCEPTED0.05 s1details
#60.05 s2details
#70.05 s2details
#80.05 s2details
#90.06 s2details
#100.05 s2details
#110.04 s3details
#120.05 s3details
#130.05 s3details
#140.06 s3details
#150.06 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:160: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;
    int 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;

    }
    
    /*
    for(auto W : walls) cout << W.start << " " << W.end << " " << W.pos << endl;
    for(auto p : corners) cout << p.first << " " << p.second << endl;
    
    if(can_see(x1,y1,x2,y2)){
        cout << abs(x1-x2) + abs(y1-y2) << endl;
    }*/
    
    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 = c1 + 1; i <= c2; i++){
                //cout << "+" << corner_distances[i] << endl;
                d += corner_distances[i];
            }
            //cout << c1 << " " << c2 << " " << d << endl;
            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;
    
    
    /*
    cout << "visible A (" << x1 << " " << y1 << ")" << endl;
    for(auto p : visible_A) cout << p.first << " " << p.second << endl;
    
    cout << "visible B (" << x2 << " " << y2 << ")" << endl;
    for(auto p : visible_B) cout << p.first << " " << p.second << endl;
    */
    
    /*
    cout << go_left(3,-1).id << " " << go_right(3,-1).id << endl;
    cout << go_up(3,-1).id << " " << go_down(3,-1).id << endl;
    
    cout << go_left(-8,3).id << " " << go_right(-8,3).id << endl;
    cout << go_up(-8,3).id << " " << go_down(-8,3).id << endl;
    */
    /*for(int i = -5; i < 6; i++){
        cout << i << " " << can_see(-3,2,i,-1) << endl;
    }*/
    /*
    for(int i = -15; i <= 15; i++){
        cout << i << " " << go_up(i,-1).id << endl;
    }*/
}


Test details

Test 1

Group: 1

Verdict:

input
6 -1 8 -2

correct output
3

user output
13

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:

input
4 4 2 7

correct output
5

user output
9

Test 5

Group: 1

Verdict: ACCEPTED

input
-5 4 -6 -3

correct output
8

user output
8

Test 6

Group: 2

Verdict:

input
-156 226 -9 7

correct output
438

user output
310

Test 7

Group: 2

Verdict:

input
403 265 10 0

correct output
1100

user output
354

Test 8

Group: 2

Verdict:

input
146 462 9 -3

correct output
1160

user output
120

Test 9

Group: 2

Verdict:

input
223 82 -1 5

correct output
725

user output
207

Test 10

Group: 2

Verdict:

input
1 390 -5 2

correct output
436

user output
376

Test 11

Group: 3

Verdict:

input
-540305713988379 -580514137141...

correct output
1233409841814111

user output
951934865103361

Test 12

Group: 3

Verdict:

input
-156703691254895 -816797859965...

correct output
1086091541904259

user output
804616565193511

Test 13

Group: 3

Verdict:

input
-438806811971369 -748477242640...

correct output
1299874045296142

user output
1018399068585410

Test 14

Group: 3

Verdict:

input
939351840049839 -9541207461566...

correct output
2118652567575152

user output
1555702614153746

Test 15

Group: 3

Verdict:

input
-840127817790022 1113515308437...

correct output
1007774343975947

user output
399600539577441