CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-11 21:47:21 +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.06 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.06 s2details
#9ACCEPTED0.06 s2details
#10ACCEPTED0.06 s2details
#11ACCEPTED0.06 s3details
#12ACCEPTED0.06 s3details
#13ACCEPTED0.06 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.06 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < jo.size(); ++i) {
                      ^

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#define F first
#define S second
using namespace std;
typedef long long ll;
unordered_map<ll, unordered_map<ll,ll> > t;
int main() {
    ll ux, uy, mx, my;
    cin>>uy>>ux>>my>>mx;
    uy = -uy;
    my = -my;
    //cin>>ux>>uy>>mx>>my;
    ll x = 0;
    ll y = 0;
    ll x2 = -1;
    ll y2 = -1;
    t[x][y] = 1;
    ll len = 2;
    for(ll i = 0; i < 6; ++i) {
        for(ll j = 0; j < len; ++j) {
            if(i%4 == 0) ++x;
            if(i%4 == 1) ++y;
            if(i%4 == 2) --x;
            if(i%4 == 3) --y; 
            t[x][y] = 1;
        }
        len *= 2;
    }
    x = 0;
    y = 0;
    len = 2;
    vector<ll> v;
    vector<pair<ll, ll> > v2;
    for(ll i = 0; i < 62; ++i) {
        if(i%2 == 0) {
            v.push_back(y);
        }
        else {
            v.push_back(x);
        }
        v2.push_back({x2, y2});
        if(i%4 == 0) x += len, x2 += len+2;
        if(i%4 == 1) y += len, y2 += len+2;
        if(i%4 == 2) x -= len, x2 -= len+2;
        if(i%4 == 3) y -= len, y2 -= len+2; 
        len *= 2;
        //cout<<x<<' '<<y<<'\n';
    }
    ll ans = 0;
    for(ll i = (int)v.size()-5; i >= 1; --i) {
        bool q = 0;
        bool w = 0;
        if(i % 2 == 1) {
            q = ux > min(v[i], v[i+4]) && ux < max(v[i], v[i+4]);
            w = mx > min(v[i], v[i+4]) && mx < max(v[i], v[i+4]);
        }
        else {
            q = uy > min(v[i], v[i+4]) && uy < max(v[i], v[i+4]);
            w = my > min(v[i], v[i+4]) && my < max(v[i], v[i+4]);
        }
        //cout<<i<<' '<<q<<' '<<w<<' '<<ux<<' '<<uy<<' '<<mx<<' '<<my<<' '<<v[i]<<' '<<v[i+4]<<'\n';
        if(q && w) {
            cout<<ans + abs(mx-ux) + abs(my-uy)<<'\n';
            return 0;
        }
        if(i % 2 == 1) {
            if(uy > min(v[i-1], v[i+3]) && uy < max(v[i-1], v[i+3])) q = 0;
            if(my > min(v[i-1], v[i+3]) && my < max(v[i-1], v[i+3])) w = 0;
        }
        else {
            if(ux > min(v[i-1], v[i+3]) && ux < max(v[i-1], v[i+3])) q = 0;
            if(mx > min(v[i-1], v[i+3]) && mx < max(v[i-1], v[i+3])) w = 0;
        }
        if(q) {
            ans += abs(v2[i].F-ux) + abs(v2[i].S-uy);
            ux = v2[i].F;
            uy = v2[i].S;
        }
        if(w) {
            ans += abs(v2[i].F-mx) + abs(v2[i].S-my);
            mx = v2[i].F;
            my = v2[i].S;
        }
    }
    vector<pair<pair<ll, ll>, ll> > jo;
    jo.push_back({{mx, my}, ans});
    for(int i = 0; i < jo.size(); ++i) {
        if(jo[i].F.F == ux && jo[i].F.S == uy) {
            cout<<jo[i].S<<'\n';
            return 0;
        }
        for(int j = 0; j < 4; ++j) {
            ll ux = jo[i].F.F;
            ll uy = jo[i].F.S;
            if(j == 0) ++ux;
            if(j == 1) --ux;
            if(j == 2) ++uy;
            if(j == 3) --uy;
            if(t[ux][uy] == 0) {
                jo.push_back({{ux, uy}, jo[i].S+1});
                t[ux][uy] = 2;
            }
        }
    }
}

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