| Task: | Labyrintti |
| Sender: | |
| Submission time: | 2015-10-11 21:23:16 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | 100 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 12 |
| #2 | ACCEPTED | 29 |
| #3 | ACCEPTED | 59 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.06 s | 1 | details |
| #2 | ACCEPTED | 0.06 s | 1 | details |
| #3 | ACCEPTED | 0.06 s | 1 | details |
| #4 | ACCEPTED | 0.06 s | 1 | details |
| #5 | ACCEPTED | 0.06 s | 1 | details |
| #6 | ACCEPTED | 0.05 s | 2 | details |
| #7 | ACCEPTED | 0.07 s | 2 | details |
| #8 | ACCEPTED | 0.06 s | 2 | details |
| #9 | ACCEPTED | 0.06 s | 2 | details |
| #10 | ACCEPTED | 0.05 s | 2 | details |
| #11 | ACCEPTED | 0.06 s | 3 | details |
| #12 | ACCEPTED | 0.06 s | 3 | details |
| #13 | ACCEPTED | 0.06 s | 3 | details |
| #14 | ACCEPTED | 0.06 s | 3 | details |
| #15 | ACCEPTED | 0.06 s | 3 | details |
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 |