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

Code

#include <iostream>
#include <cstdlib>
#include <complex>
using namespace std;
typedef long long ll;
typedef complex<ll> V;
bool start(V pt) {
	ll x=pt.real();
	ll y=pt.imag();
	return y<=-1 && y>=-3 && x<=1 && x>=-5;
}
const V ds[]={
	V(-1,0),
	V(0,1),
	V(1,0),
	V(0,-1)
};

bool betw(V a, V b, V v) {
//	cout<<"betw "<<a<<' '<<b<<' '<<v<<'\n';
	ll x1=a.real(),x2=b.real();
	ll y1=a.imag(),y2=b.imag();
	ll x=v.real(),y=v.imag();
	if (x1>x2) swap(x1,x2);
	if (y1>y2) swap(y1,y2);
	return x>=x1 && x<=x2 && y>=y1 && y<=y2;
}

bool inR(V cur, V pt, V dir, V pdir, ll w1, ll w2, ll w3) {
	V c1 = cur - w1*dir;
	V c2 = cur + w2*pdir + w3*dir;
	return betw(c1,c2,pt);
}

ll dist(V a, V b) {
	V v=b-a;
	return llabs(v.real()) + llabs(v.imag());
}

ll solve(V v1, V v2) {
	if (start(v1)&&start(v2)) {
		return dist(v1,v2);
	}
	int step=0;
	ll len=1;
	V cur(1,-1);
	int d=0;
	bool found = 0;
	ll res=0;
	while(1) {
		ll add;
		ll w1,w2,w3;
		if (step <= 1) {
			len=1;
			add = 2*len;
			w1 = len;
			w2 = 2*len;
			w3 = add+4*len;
			if (step==1) {
				w1=2;
				w2=4*len;
				w3=8*len;
			}
		} else {
			len *=2;
			add = len+2;
			w1 = 4*len - len-1;
			w2 = 8*len - 2*len;
			w3 = 16*len - 4*len + len;
		}
		++step;
		V dir=ds[d];
		V pdir=ds[(d+3)%4];
		++d;
		d%=4;

//		cout<<cur<<' '<<add<<' '<<w1<<' '<<w2<<' '<<dir<<' '<<pdir<<" ; "<<res<<'\n';
//		cout<<"from "<<cur<<" towards "<<add*dir<<" w1w2w3: "<<w1<<' '<<w2<<' '<<w3<<'\n';

		if (!found) {
			if (inR(cur, v1, dir, pdir, w1, w2, w3)
			 && inR(cur, v2, dir, pdir, w1, w2, w3)) {
//				cout<<"both\n";
				return dist(v1,v2);
			}
			bool in1 = inR(cur, v1, dir, pdir, w1, w2, add-1);
			bool in2 = inR(cur, v2, dir, pdir, w1, w2, add-1);
			if (in1 || in2) {
//				cout<<"found1 "<<in1<<in2<<'\n';
				found = 1;
				if (in1) swap(v1,v2);
			}
		} else {
			if (inR(cur, v1, dir, pdir, w1, w2, w3)) {
				res += dist(v1,v2);
				return res;
			}
		}

		cur += add*dir;
		if (found) res += dist(cur,v2), v2=cur;
	}
}

int main() {
	ll x1,y1,x2,y2;
	cin>>y1>>x1>>y2>>x2;
	V v1(x1,y1);
	V v2(x2,y2);
	cout<<solve(v1,v2)<<'\n';
}

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