CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-11 21:41:04
Language:C++
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.08 s1details
#2ACCEPTED0.07 s1details
#3ACCEPTED0.07 s1details
#4ACCEPTED0.07 s1details
#5ACCEPTED0.07 s1details
#6ACCEPTED0.20 s2details
#7--2details
#8--2details
#9ACCEPTED0.44 s2details
#10ACCEPTED0.15 s2details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details

Code

#include <bits/stdc++.h>

#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int

#define pii pair<int, int>
#define pll pair<long long, long long>

#define defmod 1000000007
using namespace std;


int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	int y1, x1, y2, x2;
	cin >> y1 >> x1 >> y2 >> x2;
	y1*=-1;
	y2*=-1;
	unordered_map<int, unordered_map<int, int> > lol;
	lol[0][0] = 0;
	int x = 0, y = 0;
	for(int i = 1; i <= 16; i++){
		if(i%4 == 1){
			for(int j = x; j <= x+(1<<i); j++)
				lol[y][j] = 0;
			x+=(1<<i);
		}
		else if(i%4 == 2){
			for(int j = y; j <= y+(1<<i); j++)
				lol[j][x] = 0;
			y+=(1<<i);
		}
		else if(i%4 == 3){
			for(int j = x; j >= x-(1<<i); j--)
				lol[y][j] = 0;
			x-=(1<<i);
		}
		else{
			for(int j = y; j >= y-(1<<i); j--)
				lol[j][x] = 0;
			y-=(1<<i);
		}
		//cout << x << ", " << y << endl;
	}
	queue<pair<int, pii> > q;
	q.push({0, {y1, x1}});
	while(!q.empty()){
		int cx = q.front().second.second;
		int cy = q.front().second.first;
		int dist = q.front().first;
		q.pop();
		if(lol[cy].count(cx))
			continue;
		//cout << "nyt " << cx << ", " << cy << endl;
		lol[cy][cx] = dist;
		if(cx == x2 && cy == y2){
			cout << dist << endl;
			return 0;
		}
		q.push({dist+1, {cy+1, cx}});
		q.push({dist+1, {cy-1, cx}});
		q.push({dist+1, {cy, cx+1}});
		q.push({dist+1, {cy, cx-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: ACCEPTED

input
-156 226 -9 7

correct output
438

user output
438

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: 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:

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)