CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-11 20:57:54 +0300
Language:C++
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.05 s1details
#60.12 s2details
#70.12 s2details
#80.14 s2details
#90.14 s2details
#100.12 s2details
#110.13 s3details
#120.13 s3details
#130.12 s3details
#140.12 s3details
#150.15 s3details

Code

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

using namespace std;

int main(void) {
  vector<vector<int>> board(25,vector<int>(25,0));
  int64_t x=0,y=0;
  for(int64_t s=0;s<10;s++) {
    if(s%4 == 0) {
      for(int i=0;i<(1 << (s+1));i++) {
        if(x+11 < 25 && x+11 >= 0 && y+11 < 25 && y+11 >= 0) board[x+11][y+11]=-1;
        x++;
      }
    } else if(s%4 == 1) {
      for(int i=0;i<(1 << (s+1));i++) {
        if(x+11 < 25 && x+11 >= 0 && y+11 < 25 && y+11 >= 0) board[x+11][y+11]=-1;
        y++;
      }
    } else if(s%4 == 2) {
      for(int i=0;i<(1 << (s+1));i++) {
        if(x+11 < 25 && x+11 >= 0 && y+11 < 25 && y+11 >= 0) board[x+11][y+11]=-1;
        x--;
      }
    } else if(s%4 == 3) {
      for(int i=0;i<(1 << (s+1));i++) {
        if(x+11 < 25 && x+11 >= 0 && y+11 < 25 && y+11 >= 0) board[x+11][y+11]=-1;
        y--;
      }
    }
  }
  int64_t x1,y1,x2,y2;
  cin >> y1 >> x1 >> y2 >> x2;
  y1=-y1;
  y2=-y2;
  queue<pair<int,int>> q;
  q.push(make_pair(x1,y1));
  while(!q.empty()) {
    pair<int,int> top=q.front();
    q.pop();
    if(top.first == x2 && top.second == y2) {
      cout << board[top.first+11][top.second+11] << endl;
      return 0;
    }
    if(top.first > -10) {
      if(board[top.first-1+11][top.second+11] == 0) {
        board[top.first-1+11][top.second+11] = board[top.first+11][top.second+11]+1;
        q.push(make_pair(top.first-1,top.second));
      }
    }
    if(top.second > -10) {
      if(board[top.first+11][top.second-1+11] == 0) {
        board[top.first+11][top.second-1+11] = board[top.first+11][top.second+11]+1;
        q.push(make_pair(top.first,top.second-1));
      }
    }
    if(top.first < 10) {
      if(board[top.first+1+11][top.second+11] == 0) {
        board[top.first+1+11][top.second+11] = board[top.first+11][top.second+11]+1;
        q.push(make_pair(top.first+1,top.second));
      }
    }
    if(top.second > -10) {
      if(board[top.first+11][top.second+1+11] == 0) {
        board[top.first+11][top.second+1+11] = board[top.first+11][top.second+11]+1;
        q.push(make_pair(top.first,top.second+1));
      }
    }
  }
  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
(empty)

Test 7

Group: 2

Verdict:

input
403 265 10 0

correct output
1100

user output
(empty)

Test 8

Group: 2

Verdict:

input
146 462 9 -3

correct output
1160

user output
(empty)

Test 9

Group: 2

Verdict:

input
223 82 -1 5

correct output
725

user output
(empty)

Test 10

Group: 2

Verdict:

input
1 390 -5 2

correct output
436

user output
(empty)

Test 11

Group: 3

Verdict:

input
-540305713988379 -580514137141...

correct output
1233409841814111

user output
(empty)

Test 12

Group: 3

Verdict:

input
-156703691254895 -816797859965...

correct output
1086091541904259

user output
(empty)

Test 13

Group: 3

Verdict:

input
-438806811971369 -748477242640...

correct output
1299874045296142

user output
(empty)

Test 14

Group: 3

Verdict:

input
939351840049839 -9541207461566...

correct output
2118652567575152

user output
(empty)

Test 15

Group: 3

Verdict:

input
-840127817790022 1113515308437...

correct output
1007774343975947

user output
(empty)