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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:33:15: warning: unused variable 'um' [-Wunused-variable]
     long long um = 0;
               ^
input/code.cpp:34:15: warning: unused variable 'mm' [-Wunused-variable]
     long long mm = 0;
               ^

Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>

#define uint unsigned int
#define INF 999999999
#define ll long long
#define M 1000000007
#define E 0.0000001
#define N 131072

using namespace std;

int c[4000][4000];

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    long long x1, x2, y1, y2;
    cin>>y1>>x1>>y2>>x2;

    long long x = 0;
    long long y = 0;
    long long i = 0;
    long long ua = -1;
    long long ma = -1;
    long long um = 0;
    long long mm = 0;
    long long l = 2;
    long long cx = -1;
    long long cy = -1;
    long long cl = -1;
    long long ci = -1;
    if (abs(x1) > 500 || abs(x2) > 500 || abs(y1) > 500 || abs(x2) > 500) {
        while (ua == -1 || ma == -1) {
            switch (i % 4) {
                case 0:
                    if (ua == -1) if (x1 >= x && x1 < x + l && y1 < y && y1 > y - 2 * l) ua = i;
                    if (ma == -1) if (x2 >= x && x2 < x + l && y2 < y && y2 > y - 2 * l) ma = i;
                    x += l;
                    break;
                case 1:
                    if (ua == -1) if (x1 < x && x1 > x - 2 * l && y1 <= y && y1 > y - l) ua = i;
                    if (ma == -1) if (x2 < x && x2 > x - 2 * l && y2 <= y && y2 > y - l) ma = i;
                    y -= l;
                    break;
                case 2:
                    if (ua == -1) if (x1 <= x && x1 > x - l && y1 > y && y1 < y + 2 * l) ua = i;
                    if (ma == -1) if (x2 <= x && x2 > x - l && y2 > y && y2 < y + 2 * l) ma = i;
                    x -= l;
                    break;
                case 3:
                    if (ua == -1) if (x1 > x && x1 < x + 2 * l && y1 >= y && y1 < y + l) ua = i;
                    if (ma == -1) if (x2 > x && x2 < x + 2 * l && y2 >= y && y2 < y + l) ma = i;
                    y += l;
                    break;
            }
            if (ua == -1 && ma == -1) {
                switch (i % 4) {
                    case 0:
                        cy += l;
                        break;
                    case 1:
                        cx += l;
                        break;
                    case 2:
                        cy -= l;
                        break;
                    case 3:
                        cx -= l;
                        break;
                }
                cl = l * 2;
                ci = i;
            }

            l *= 2;
            i++;
        }

        if (ua > ma) {
            swap(ua, ma);
            swap(y1, y2);
            swap(x1, x2);
        }

        if (ma - ua <= 1) {
            cout<<abs(x1-x2)+abs(y1-y2)<<endl;
        } else {
            //cout<<"moving to corner by taking "<<abs(x1-cx)+abs(y1-cy)<<" steps..."<<endl;
            long long ans = abs(x1-cx)+abs(y1-cy);
            x1 = cx;
            y1 = cy;
            cl /= 2;
            while (ma - ua > 1) {
                ua++;
                ans += 2 + cl;
                //cout<<"corner is at ("<<y1<<", "<<x1<<"), moving "<<2 + cl<<" steps..."<<endl;
                switch (ci % 4) {
                    case 0:
                        x1 += cl + 2;
                        break;
                    case 1:
                        y1 -= cl + 2;
                        break;
                    case 2:
                        x1 -= cl + 2;
                        break;
                    case 3:
                        y1 += cl + 2;
                        break;
                }
                //cout<<"now at ("<<y1<<", "<<x1<<")..."<<endl;
                cl *= 2;
                ci++;
            }
            cout<<ans + abs(x1-x2)+abs(y1-y2)<<endl;
        }
    } else {
        int w = 8 * (int)max(abs(x1), abs(x2)) + 1;
        int h = 8 * (int)max(abs(y1), abs(y2)) + 1;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                c[y][x] = 999999999;
            }
        }
        int x = w / 2;
        int y = h / 2;
        int t = 2;
        int i = 0;

        while (x >= 0 && x < w && y >= 0 && y < h) {
            for (int b = 0; b < t; b++) {
                c[y][x] = -1;
                switch (i % 4) {
                    case 0:
                        x++;
                        break;
                    case 1:
                        y--;
                        break;
                    case 2:
                        x--;
                        break;
                    case 3:
                        y++;
                        break;
                }
                if (!(x >= 0 && x < w && y >= 0 && y < h)) break;
            }
            t *= 2;
            i++;
        }

        queue<pair<int, int>> q;
        q.push(make_pair(x1 + w / 2, y1 + h / 2));
        c[y1 + h / 2][x1 + w / 2] = 0;
        while (q.size() > 0) {
            pair<int, int> p = q.front();
            q.pop();
            int y = p.second;
            int x = p.first;
            if (y > 0 && c[y - 1][x] > c[y][x] + 1) {
                c[y - 1][x] = c[y][x] + 1;
                q.push(make_pair(x, y - 1));
            }
            if (x > 0 && c[y][x - 1] > c[y][x] + 1) {
                c[y][x - 1] = c[y][x] + 1;
                q.push(make_pair(x - 1, y));
            }
            if (y < h - 1 && c[y + 1][x] > c[y][x] + 1) {
                c[y + 1][x] = c[y][x] + 1;
                q.push(make_pair(x, y + 1));
            }
            if (x < w - 1 && c[y][x + 1] > c[y][x] + 1) {
                c[y][x + 1] = c[y][x] + 1;
                q.push(make_pair(x + 1, y));
            }
        }

        /*for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                cout<<c[y][x]<<" ";
            }
            cout<<endl;
        }*/

        cout<<c[y2 + h / 2][x2 + w / 2]<<endl;
    }

    return 0;
}

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