CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-10 00:11:30 +0300
Language:C++
Status:READY
Result:71
Feedback
groupverdictscore
#1ACCEPTED12
#20
#3ACCEPTED59
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.07 s2details
#8ACCEPTED0.07 s2details
#9ACCEPTED0.06 s2details
#100.05 s2details
#11ACCEPTED0.05 s3details
#12ACCEPTED0.05 s3details
#13ACCEPTED0.05 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.05 s3details

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[2000][2000];
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 = 4 * (int)max(abs(x1), abs(x2)) + 1;
int h = 4 * (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

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:

input
1 390 -5 2

correct output
436

user output
394

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