CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-09 23:41:32 +0300
Language:C++
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.05 s1details
#60.05 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.05 s2details
#90.05 s2details
#100.05 s2details
#110.07 s3details
#120.06 s3details
#130.05 s3details
#140.07 s3details
#150.06 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:30:9: warning: unused variable 'um' [-Wunused-variable]
     int um = 0;
         ^
input/code.cpp:31:9: warning: unused variable 'mm' [-Wunused-variable]
     int mm = 0;
         ^

Code

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

#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 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;
    int i = 0;
    int ua = -1;
    int ma = -1;
    int um = 0;
    int mm = 0;
    long long l = 2;
    int cx = -1;
    int cy = -1;
    int cl = -1;
    int ci = -1;
    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;
    }

    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:

input
-156 226 -9 7

correct output
438

user output
446

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:

input
223 82 -1 5

correct output
725

user output
729

Test 10

Group: 2

Verdict:

input
1 390 -5 2

correct output
436

user output
448

Test 11

Group: 3

Verdict:

input
-540305713988379 -580514137141...

correct output
1233409841814111

user output
1120821569116767

Test 12

Group: 3

Verdict:

input
-156703691254895 -816797859965...

correct output
1086091541904259

user output
973503269206915

Test 13

Group: 3

Verdict:

input
-438806811971369 -748477242640...

correct output
1299874045296142

user output
1187285772598798

Test 14

Group: 3

Verdict:

input
939351840049839 -9541207461566...

correct output
2118652567575152

user output
1893476022180464

Test 15

Group: 3

Verdict:

input
-840127817790022 1113515308437...

correct output
1007774343975947

user output
951475912659979