CSES - Putka Open 2015 – 4/6

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
group	verdict	score
#1	ACCEPTED	12
#2	ACCEPTED	29
#3	ACCEPTED	59

Test results
test	verdict	time	group
#1	ACCEPTED	0.06 s	1	details
#2	ACCEPTED	0.06 s	1	details
#3	ACCEPTED	0.05 s	1	details
#4	ACCEPTED	0.06 s	1	details
#5	ACCEPTED	0.06 s	1	details
#6	ACCEPTED	0.07 s	2	details
#7	ACCEPTED	0.17 s	2	details
#8	ACCEPTED	0.11 s	2	details
#9	ACCEPTED	0.07 s	2	details
#10	ACCEPTED	0.06 s	2	details
#11	ACCEPTED	0.05 s	3	details
#12	ACCEPTED	0.05 s	3	details
#13	ACCEPTED	0.07 s	3	details
#14	ACCEPTED	0.06 s	3	details
#15	ACCEPTED	0.06 s	3	details

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` view save

correct output
`3` view save

user output
`3` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`-8 2 8 -9` view save

correct output
`27` view save

user output
`27` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`3 2 -5 -1` view save

correct output
`13` view save

user output
`13` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`4 4 2 7` view save

correct output
`5` view save

user output
`5` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`-5 4 -6 -3` view save

correct output
`8` view save

user output
`8` view save

Test 6

Group: 2

Verdict: ACCEPTED

input
`-156 226 -9 7` view save

correct output
`438` view save

user output
`438` view save

Test 7

Group: 2

Verdict: ACCEPTED

input
`403 265 10 0` view save

correct output
`1100` view save

user output
`1100` view save

Test 8

Group: 2

Verdict: ACCEPTED

input
`146 462 9 -3` view save

correct output
`1160` view save

user output
`1160` view save

Test 9

Group: 2

Verdict: ACCEPTED

input
`223 82 -1 5` view save

correct output
`725` view save

user output
`725` view save

Test 10

Group: 2

Verdict: ACCEPTED

input
`1 390 -5 2` view save

correct output
`436` view save

user output
`436` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`-540305713988379 -580514137141...` view save

correct output
`1233409841814111` view save

user output
`1233409841814111` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`-156703691254895 -816797859965...` view save

correct output
`1086091541904259` view save

user output
`1086091541904259` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`-438806811971369 -748477242640...` view save

correct output
`1299874045296142` view save

user output
`1299874045296142` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`939351840049839 -9541207461566...` view save

correct output
`2118652567575152` view save

user output
`2118652567575152` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`-840127817790022 1113515308437...` view save

correct output
`1007774343975947` view save

user output
`1007774343975947` view save

Putka Open 2015 – 4/6

Labyrintti

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions ()