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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:205:50: warning: 'block2pcy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   steps+=abs(block2pcx - x2) + abs(block2pcy - y2);
                                                  ^
input/code.cpp:205:28: warning: 'block2pcx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   steps+=abs(block2pcx - x2) + abs(block2pcy - y2);
                            ^
input/code.cpp:196:55: warning: 'block2cy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int64_t steps=abs(x1 - block1cx) + abs(y1 - block1cy);
                                                       ^
input/code.cpp:196:34: warning: 'block2cx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int64_t steps=abs(x1 - block1cx) + abs(y1 - block1cy);
                                  ^

Code

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<utility>

using namespace std;

int main(void) {
  int64_t y1,x1,y2,x2;
  cin >> y1 >> x1 >> y2 >> x2;
  y1=-y1;
  y2=-y2;

  int64_t block1cx,block1cy,block2cx,block2cy,block1pcx,block1pcy,block2pcx,block2pcy;
  int64_t block1=-1,block2=-1;
  int64_t found=2;
  if(x1 <= 2 && y1 <= 4 && x1 >= 0 && y1 >= 0) {
    found--;
    block1=0;
    block1cx=0;
    block1cy=0;
    block1pcx=0;
    block1pcy=0;
  } else if(x1 >= -6 && x1 < 0 && y1 >= -12 && y1 <= 4) {
    found--;
    block1=1;
    block1cx=-1;
    block1cy=-1;
    block1pcx=-1;
    block1pcy=-1;
  }
  if(x2 <= 2 && y2 <= 4 && x2 >= 0 && y2 >= 0) {
    found--;
    block2=0;
    block2cx=0;
    block2cy=0;
    block2pcx=0;
    block2pcy=0;
  } else if(x2 >= -6 && x2 < 0 && y2 >= -12 && y2 <= 4) {
    found--;
    block2=1;
    block2cx=-1;
    block2cy=-1;
    block2pcx=-1;
    block2pcy=-1;
  }

  int64_t cornerx=-6, cornery=-12;
  int64_t cornerx0=0, cornery0=0;
  int64_t step=0;
  int64_t jump=32;
  int64_t blocknum=2;
  int64_t width=16,height=5;
  while(found>0) {
    if(step%4 == 0) {
      width=jump-height-1;
      height=cornery0 - cornery-1;
      cornerx+=jump;
      cornerx0+=jump/16;
      /*cout << "RIGHT!\n";
      cout << cornerx-width << " to " << cornerx << endl;
      cout << cornery << " to " << cornery+height << endl;*/
      if(y1 >= cornery && y1 <= cornery+height && x1 <= cornerx && x1 >= cornerx - width) {
        block1=blocknum;
        block1cx=cornerx0+1;
        block1cy=cornery0-1;
        block1pcx=cornerx0-jump/16-1;
        block1pcy=cornery0-1;
        found--;
      }
      if(y2 >= cornery && y2 <= cornery+height && x2 <= cornerx && x2 >= cornerx - width) {
        block2=blocknum;
        block2cx=cornerx0+1;
        block2cy=cornery0-1;
        block2pcx=cornerx0-jump/16-1;
        block2pcy=cornery0-1;
        found--;
      }
    } else if(step%4 == 1) {
      width=jump-height-1;
      height=cornerx - cornerx0-1;
      cornery+=jump;
      cornery0+=jump/16;
      /*cout << "UP!\n";
      cout << cornerx-height << " to " << cornerx << endl;
      cout << cornery-width << " to " << cornery << endl;*/

      if(y1 >= cornery-width && y1 <= cornery && x1 <= cornerx && x1 >= cornerx - height) {
        block1=blocknum;
        block1cx=cornerx0+1;
        block1cy=cornery0+1;
        block1pcx=cornerx0+1;
        block1pcy=cornery0-jump/16-1;
        found--;
      }
      if(y2 >= cornery-width && y2 <= cornery && x2 <= cornerx && x2 >= cornerx - height) {
        block2=blocknum;
        block2cx=cornerx0+1;
        block2cy=cornery0+1;
        block2pcx=cornerx0+1;
        block2pcy=cornery0-jump/16-1;
        found--;
      }
    } else if(step%4 == 2) {
      width=jump-height-1;
      height=cornery - cornery0-1;
      cornerx-=jump;
      cornerx0-=jump/16;
      if(y1 >= cornery-height && y1 <= cornery && x1 <= cornerx+width && x1 >= cornerx) {
        block1=blocknum;
        block1cx=cornerx0-1;
        block1cy=cornery0+1;
        block1pcx=cornerx0+jump/16+1;
        block1pcy=cornery0+1;
        found--;
      }
      if(y2 >= cornery-height && y2 <= cornery && x2 <= cornerx+width && x2 >= cornerx) {
        block2=blocknum;
        block2cx=cornerx0-1;
        block2cy=cornery0+1;
        block2pcx=cornerx0+jump/16+1;
        block2pcy=cornery0+1;
        found--;
      }
    } else if(step%4 == 3) {
      width=jump-height-1;
      height=cornerx0 - cornerx-1;
      cornery-=jump;
      cornery0-=jump/16;
      /*cout << "DOWN\n";
      cout << cornerx << " to " << cornerx+height << endl;
      cout << cornery << " to " << cornery+width << endl;*/

      if(y1 >= cornery && y1 <= cornery+width && x1 <= cornerx+height && x1 >= cornerx) {
        block1=blocknum;
        block1cx=cornerx0-1;
        block1cy=cornery0-1;
        block1pcx=cornerx0-1;
        block1pcy=cornery0+jump/16+1;
        found--;
      }
      if(y2 >= cornery && y2 <= cornery+width && x2 <= cornerx+height && x2 >= cornerx) {
        block2=blocknum;
        block2cx=cornerx0-1;
        block2cy=cornery0-1;
        block2pcx=cornerx0-1;
        block2pcy=cornery0+jump/16+1;
        found--;
      }
    }
    jump*=2;
    step++;
    blocknum++;
  }

  if(block2 < block1) {
    swap(block2,block1);
    swap(block2cx,block1cx);
    swap(block2cy,block1cy);
    swap(block2pcx,block1pcx);
    swap(block2pcy,block1pcy);
    swap(x1,x2);
    swap(y1,y2);
  }

  if(abs(block1 - block2) <= 1) {
    cout << abs(x1 - x2) + abs(y1 - y2) << endl;
    return 0;
  }

  if(block1 == 0) {
    if(block2 == 1) {
      cout << abs(x1 - x2) + abs(y1 - y2) << endl;
      return 0;
    } else {
      int64_t steps=0;
      steps+=abs(x1 + 1) + abs(y1 + 1);
      int64_t nextstep=2;
      for(int64_t i=2;i<=block2-1;i++) {
        steps+=nextstep+2;
        nextstep*=2;
      }
      steps+=abs(block2pcx - x2) + abs(block2pcy - y2);
      cout << steps << endl;
      return 0;
    }
  }

  /*cout << "HERE!" << block1 << " " << block2 << endl;
  cout << block1cx << "," << block1cy << endl;
  cout << block1pcx << "," << block1pcy << endl;*/

  int64_t steps=abs(x1 - block1cx) + abs(y1 - block1cy);
  //cout << "Moving to da place: " << steps << endl;
  int64_t nextstep=((int64_t) 1) << ((int64_t) block1);
  for(int64_t i=block1;i<block2-1;i++) {
    //cout << "Adding steps: " << nextstep+2 << endl;
    steps+=nextstep+2;
    nextstep*=2;
  }
  //cout << block2pcx << "," << block2pcy << endl;
  steps+=abs(block2pcx - x2) + abs(block2pcy - y2);
  cout << steps << 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