| Task: | Labyrintti |
| Sender: | |
| Submission time: | 2015-10-11 21:46:33 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | 0 |
| group | verdict | score |
|---|---|---|
| #1 | WRONG ANSWER | 0 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.07 s | 1 | details |
| #2 | WRONG ANSWER | 0.05 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 | WRONG ANSWER | 0.06 s | 2 | details |
| #7 | ACCEPTED | 0.07 s | 2 | details |
| #8 | ACCEPTED | 0.06 s | 2 | details |
| #9 | WRONG ANSWER | 0.06 s | 2 | details |
| #10 | WRONG ANSWER | 0.06 s | 2 | details |
| #11 | ACCEPTED | 0.06 s | 3 | details |
| #12 | ACCEPTED | 0.06 s | 3 | details |
| #13 | WRONG ANSWER | 0.05 s | 3 | details |
| #14 | ACCEPTED | 0.06 s | 3 | details |
| #15 | WRONG ANSWER | 0.07 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()':
input/code.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < jo.size(); ++i) {
^Code
#include <iostream>
#include <vector>
#include <unordered_map>
#define F first
#define S second
using namespace std;
typedef long long ll;
unordered_map<ll, unordered_map<ll,ll> > t;
int main() {
ll ux, uy, mx, my;
cin>>uy>>ux>>my>>mx;
uy = -uy;
my = -my;
//cin>>ux>>uy>>mx>>my;
ll x = 0;
ll y = 0;
ll x2 = -1;
ll y2 = -1;
t[x][y] = 1;
ll len = 2;
for(ll i = 0; i < 6; ++i) {
for(ll j = 0; j < len; ++j) {
if(i%4 == 0) ++x;
if(i%4 == 1) ++y;
if(i%4 == 2) --x;
if(i%4 == 3) --y;
t[x][y] = 1;
}
len *= 2;
}
x = 0;
y = 0;
len = 2;
vector<ll> v;
vector<pair<ll, ll> > v2;
for(ll i = 0; i < 62; ++i) {
if(i%2 == 0) {
v.push_back(y);
}
else {
v.push_back(x);
}
v2.push_back({x2, y2});
if(i%4 == 0) x += len, x2 += len+2;
if(i%4 == 1) y += len, y2 += len+2;
if(i%4 == 2) x -= len, x2 -= len+2;
if(i%4 == 3) y -= len, y2 -= len+2;
len *= 2;
//cout<<x<<' '<<y<<'\n';
}
ll ans = 0;
for(ll i = (int)v.size()-5; i >= 1; --i) {
bool q = 0;
bool w = 0;
if(i % 2 == 1) {
q = ux > min(v[i], v[i+4]) && ux < max(v[i], v[i+4]);
w = mx > min(v[i], v[i+4]) && mx < max(v[i], v[i+4]);
}
else {
q = uy > min(v[i], v[i+4]) && uy < max(v[i], v[i+4]);
w = my > min(v[i], v[i+4]) && my < max(v[i], v[i+4]);
}
//cout<<i<<' '<<q<<' '<<w<<' '<<ux<<' '<<uy<<' '<<mx<<' '<<my<<' '<<v[i]<<' '<<v[i+4]<<'\n';
if(q && w) {
cout<<abs(mx-ux) + abs(my-uy)<<'\n';
return 0;
}
if(i % 2 == 1) {
if(uy > min(v[i-1], v[i+3]) && uy < max(v[i-1], v[i+3])) q = 0;
if(my > min(v[i-1], v[i+3]) && my < max(v[i-1], v[i+3])) w = 0;
}
else {
if(ux > min(v[i-1], v[i+3]) && ux < max(v[i-1], v[i+3])) q = 0;
if(mx > min(v[i-1], v[i+3]) && mx < max(v[i-1], v[i+3])) w = 0;
}
if(q) {
ans += abs(v2[i].F-ux) + abs(v2[i].S-uy);
ux = v2[i].F;
uy = v2[i].S;
}
if(w) {
ans += abs(v2[i].F-mx) + abs(v2[i].S-my);
mx = v2[i].F;
my = v2[i].S;
}
}
vector<pair<pair<ll, ll>, ll> > jo;
jo.push_back({{mx, my}, ans});
for(int i = 0; i < jo.size(); ++i) {
if(jo[i].F.F == ux && jo[i].F.S == uy) {
cout<<jo[i].S<<'\n';
return 0;
}
for(int j = 0; j < 4; ++j) {
ll ux = jo[i].F.F;
ll uy = jo[i].F.S;
if(j == 0) ++ux;
if(j == 1) --ux;
if(j == 2) ++uy;
if(j == 3) --uy;
if(t[ux][uy] == 0) {
jo.push_back({{ux, uy}, jo[i].S+1});
t[ux][uy] = 2;
}
}
}
}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 6 -1 8 -2 |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 2
Group: 1
Verdict: WRONG ANSWER
| input |
|---|
| -8 2 8 -9 |
| correct output |
|---|
| 27 |
| user output |
|---|
| 12 |
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: WRONG ANSWER
| input |
|---|
| -156 226 -9 7 |
| correct output |
|---|
| 438 |
| user output |
|---|
| 18 |
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: WRONG ANSWER
| input |
|---|
| 223 82 -1 5 |
| correct output |
|---|
| 725 |
| user output |
|---|
| 6 |
Test 10
Group: 2
Verdict: WRONG ANSWER
| input |
|---|
| 1 390 -5 2 |
| correct output |
|---|
| 436 |
| user output |
|---|
| 9 |
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: WRONG ANSWER
| input |
|---|
| -438806811971369 -748477242640... |
| correct output |
|---|
| 1299874045296142 |
| user output |
|---|
| 7 |
Test 14
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 939351840049839 -9541207461566... |
| correct output |
|---|
| 2118652567575152 |
| user output |
|---|
| 2118652567575152 |
Test 15
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| -840127817790022 1113515308437... |
| correct output |
|---|
| 1007774343975947 |
| user output |
|---|
| 17 |