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

Code

#include <iostream>
#define ll long long

using namespace std;

ll a[62],b[62];
int typ[62];
ll y1,x1,y2,x2;
ll ry1,rx1,ry2,rx2;

ll dist(ll yeka, ll xeka, ll ytoka, ll xtoka) {
	if (yeka < ytoka) swap(yeka,ytoka);
	if (xeka<xtoka) swap(xeka,xtoka);
	return (yeka-ytoka) + (xeka-xtoka);
}

int contain(ll alay, ll alax, ll ylay, ll ylax, ll y, ll x) {
	if (alay>ylay) swap(alay,ylay);
	if (alax>ylax) swap(alax,ylax);
	if (y<alay || y>ylay) return 0;
	if (x<alax || x>ylax) return 0;
	return 1;
}

void findrect(int ind, int cor){
	if (cor){
                if (typ[ind]==0) {
                                ry1=a[ind]+1;
                                rx1=b[ind]+1;
                                ry2=a[ind+4]-1;
                                rx2=b[ind+4]-1;
                        } else if (typ[ind]==1) {
                                ry1=a[ind]-1;
                                rx1=b[ind]+1;
                                ry2=a[ind+4]+1;
                                rx2=b[ind+4]-1;
                        } else if (typ[ind]==2) {
                                ry1=a[ind]-1;
                                rx1=b[ind]-1;
                                ry2=a[ind+4]+1;
                                rx2=b[ind+4]+1;
                        } else {
                                ry1=a[ind]+1;
                                rx1=b[ind]-1;
                                ry2=a[ind+4]-1;
                                rx2=b[ind+4]+1;
                        }
                } else {
                        if (typ[ind]==0) {
                                ry1=a[ind];
                                rx1=b[ind]+1;
                                ry2=a[ind+1];
                                rx2=b[ind+4]-1;
                        } else if (typ[ind]==1) {
                                ry1=a[ind]-1;
                                rx1=b[ind];
                                ry2=a[ind+4]+1;
                                rx2=b[ind+1];
                        } else if (typ[ind]==2) {
                                ry1=a[ind];
                                rx1=b[ind]-1;
                                ry2=a[ind+1];
                                rx2=b[ind+4]+1;
                        } else {
                                ry1=a[ind]+1;
                                rx1=b[ind];
                                ry2=a[ind+4]-1;
                                rx2=b[ind+1];
                        }
                }
}

ll advance(int ind,int cor) {
	ll hlp1,hlp2;
	if (typ[ind]==0) {
		hlp1=a[ind+(!cor)]-(!cor);
		hlp2=x1;
	} else if (typ[ind]==1) {
		hlp1=y1;
		hlp2=b[ind+(!cor)]-(!cor);
	} else if (typ[ind]==2) {
		hlp1=a[ind+(!cor)]+(!cor);
		hlp2=x1;
	} else {
		hlp1=y1;
		hlp2=b[ind+(!cor)]+(!cor);
	}
	ll ret = dist(y1,x1,hlp1,hlp2);
	y1=hlp1;
	x1=hlp2;
	return ret;
}

int main() {
	cin >> y1 >> x1 >> y2 >> x2;
	if (contain(-3,-5,0,1,y1,x1) && contain(-3,-5,0,1,y2,x2)) {
		cout << dist(y1,x1,y2,x2) << "\n";
		return 0;
	}
	ll sel = 0;
	a[0]=0;
	b[0]=0;
	typ[0]=3;
	for (ll i=1;i<=60;i++) {
		if (sel%2) {
			b[i]=b[i-1];
			a[i]=a[i-1]+(2*((sel/2)%2)-1)*(((ll)1)<<i);
		} else {
			a[i]=a[i-1];
			b[i]=b[i-1]+(1-2*((sel/2)%2))*(((ll)1)<<i);
		}
		typ[i]=sel;
		sel++;
		sel%=4;
	}
	int found=0;
	ll res = 0;
	if (contain(-3,-5,0,1,y2,x2)) {
		swap(y1,y2);
		swap(x1,x2);
	}
	if (contain(-3,-5,0,1,y1,x1)) {
		found=1;
		ll hlp = min(x1,(ll)(-1));
		res+=dist(y1,x1,1,hlp);
		y1=1;
		x1=hlp;
	}
	int cor=1;
	int ind = 0;
	while (!found) {
		findrect(ind,cor);
		if (contain(ry1,rx1,ry2,rx2,y2,x2)) {
			swap(y1,y2);
			swap(x1,x2);
		}
		if (contain(ry1,rx1,ry2,rx2,y1,x1)) {
			found=1;
			continue;
		}
		cor = !cor;
		if (cor) ind++;
	}
	while (1) {
		findrect(ind,cor);
		if (contain(ry1,rx1,ry2,rx2,y2,x2)) {
			res+=dist(y1,x1,y2,x2);
			cout << res << "\n";
			return 0;
		}
		res+=advance(ind,cor);
		cor=!cor;
		if (cor) ind++;
	}
}

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