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

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

vector<pair<pair<ll, ll>, pair<ll, ll> > > wa;
ll d[111][111];

int bw(ll p1, ll p2, ll p){
	if (p1<=p&&p<=p2) return 1;
	if (p2<=p&&p<=p1) return 1;
	return 0;
}

ll can(ll x1, ll y1, ll x2, ll y2){
	if (x1>x2) swap(x1, x2);
	if (y1>y2) swap(y1, y2);
	for (auto w:wa){
		int xv=0;
		int yv=0;
		if (bw(w.F.F, w.S.F, x1)) xv=1;
		if (bw(w.F.F, w.S.F, x2)) xv=1;
		if (bw(x1, x2, w.F.F)) xv=1;
		if (bw(x1, x2, w.S.F)) xv=1;
		
		if (bw(w.F.S, w.S.S, y1)) yv=1;
		if (bw(w.F.S, w.S.S, y2)) yv=1;
		if (bw(y1, y2, w.F.S)) yv=1;
		if (bw(y1, y2, w.S.S)) yv=1;
		
		if (xv&&yv) return 0;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tx=0;
	ll ty=0;
	ll k=2;
	int di=0;
	vector<ll> xc;
	vector<ll> yc;
	while (k<(ll)1e17){
		ll nx=tx;
		ll ny=ty;
		if (di==0){
			nx=tx+k;
		}
		else if(di==1){
			ny=ty-k;
		}
		else if(di==2){
			nx=tx-k;
		}
		else if(di==3){
			ny=ty+k;
		}
		wa.push_back({{tx, ty}, {nx, ny}});
		xc.push_back(tx);
		xc.push_back(tx-1);
		xc.push_back(tx+1);
		yc.push_back(ty);
		yc.push_back(ty-1);
		yc.push_back(ty+1);
		k*=2;
		di++;
		di%=4;
		tx=nx;
		ty=ny;
	}
	ll y1,x1,y2,x2;
	cin>>y1>>x1>>y2>>x2;
	xc.push_back(x1);
	xc.push_back(x2);
	yc.push_back(y1);
	yc.push_back(y2);
	sort(xc.begin(), xc.end());
	xc.erase(unique(xc.begin(), xc.end()), xc.end());
	sort(yc.begin(), yc.end());
	yc.erase(unique(yc.begin(), yc.end()), yc.end());
	
	int gx=0;
	int gy=0;
	
	priority_queue<pair<ll, pair<int, int> > > dij;
	for (int i=0;i<(int)xc.size();i++){
		for (int ii=0;ii<(int)yc.size();ii++){
			if (xc[i]==x1&&yc[ii]==y1){
				dij.push({-1, {i, ii}});
			}
			if (xc[i]==x2&&yc[ii]==y2){
				gx=i;
				gy=ii;
			}
		}
	}
	while (!dij.empty()){
		auto x=dij.top();
		dij.pop();
		if (d[x.S.F][x.S.S]) continue;
		d[x.S.F][x.S.S]=-x.F;
		if (x.S.F==gx&&x.S.S==gy){
			cout<<-x.F-1<<endl;
			return 0;
		}
		for (int i=0;i<(int)xc.size();i++){
			if (i!=x.S.F){
				if (can(xc[x.S.F], yc[x.S.S], xc[i], yc[x.S.S])){
					dij.push({x.F-abs(xc[x.S.F]-xc[i]), {i, x.S.S}});
				}
			}
		}
		
		for (int i=0;i<(int)yc.size();i++){
			if (i!=x.S.S){
				if (can(xc[x.S.F], yc[x.S.S], xc[x.S.F], yc[i])){
					dij.push({x.F-abs(yc[x.S.S]-yc[i]), {x.S.F, i}});
				}
			}
		}
	}
}

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