| Task: | Island |
| Sender: | FZiuzin |
| Submission time: | 2026-04-16 12:38:23 +0300 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | 0 |
| subtask | verdict | score |
|---|---|---|
| #1 | WRONG ANSWER | 0 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| #4 | WRONG ANSWER | 0 |
| #5 | WRONG ANSWER | 0 |
| test | verdict | time | subtask | |
|---|---|---|---|---|
| #1 | WRONG ANSWER | 0.00 s | 1, 5 | details |
| #2 | WRONG ANSWER | 0.00 s | 1, 2, 3, 4, 5 | details |
| #3 | WRONG ANSWER | 0.02 s | 1, 5 | details |
| #4 | WRONG ANSWER | 0.02 s | 1, 5 | details |
| #5 | WRONG ANSWER | 0.02 s | 1, 3, 5 | details |
| #6 | WRONG ANSWER | 0.02 s | 1, 2, 4, 5 | details |
| #7 | WRONG ANSWER | 0.02 s | 1, 2, 4, 5 | details |
| #8 | WRONG ANSWER | 0.02 s | 1, 5 | details |
| #9 | WRONG ANSWER | 0.02 s | 1, 5 | details |
| #10 | WRONG ANSWER | 0.02 s | 1, 3, 4, 5 | details |
| #11 | WRONG ANSWER | 0.02 s | 1, 3, 5 | details |
| #12 | WRONG ANSWER | 0.01 s | 1, 4, 5 | details |
| #13 | WRONG ANSWER | 0.02 s | 1, 3, 4, 5 | details |
| #14 | WRONG ANSWER | 0.02 s | 1, 4, 5 | details |
| #15 | WRONG ANSWER | 0.02 s | 1, 5 | details |
| #16 | WRONG ANSWER | 0.01 s | 1, 5 | details |
| #17 | WRONG ANSWER | 0.01 s | 1, 5 | details |
| #18 | WRONG ANSWER | 0.02 s | 1, 5 | details |
| #19 | WRONG ANSWER | 0.61 s | 2, 4, 5 | details |
| #20 | WRONG ANSWER | 0.62 s | 2, 4, 5 | details |
| #21 | WRONG ANSWER | 0.60 s | 2, 4, 5 | details |
| #22 | WRONG ANSWER | 0.34 s | 2, 4, 5 | details |
| #23 | WRONG ANSWER | 0.69 s | 3, 5 | details |
| #24 | WRONG ANSWER | 0.71 s | 3, 5 | details |
| #25 | WRONG ANSWER | 0.69 s | 3, 5 | details |
| #26 | WRONG ANSWER | 0.53 s | 3, 5 | details |
| #27 | WRONG ANSWER | 0.51 s | 3, 4, 5 | details |
| #28 | WRONG ANSWER | 0.50 s | 3, 4, 5 | details |
| #29 | WRONG ANSWER | 0.65 s | 4, 5 | details |
| #30 | WRONG ANSWER | 0.66 s | 4, 5 | details |
| #31 | WRONG ANSWER | 0.37 s | 4, 5 | details |
| #32 | WRONG ANSWER | 0.37 s | 4, 5 | details |
| #33 | WRONG ANSWER | 0.37 s | 4, 5 | details |
| #34 | WRONG ANSWER | 0.51 s | 4, 5 | details |
| #35 | WRONG ANSWER | 0.64 s | 5 | details |
| #36 | WRONG ANSWER | 0.64 s | 5 | details |
| #37 | WRONG ANSWER | 0.63 s | 5 | details |
| #38 | WRONG ANSWER | 0.63 s | 5 | details |
| #39 | WRONG ANSWER | 0.55 s | 5 | details |
| #40 | WRONG ANSWER | 0.54 s | 5 | details |
| #41 | WRONG ANSWER | 0.48 s | 5 | details |
| #42 | WRONG ANSWER | 0.51 s | 5 | details |
| #43 | WRONG ANSWER | 0.53 s | 5 | details |
| #44 | WRONG ANSWER | 0.54 s | 5 | details |
Code
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define all(a) a.begin(), a.end()
#define pb push_back
const int MAXN = 1005;
const int INF = 1e14;
int ind[MAXN][MAXN];
int n,q;
bool left_wall = false;
vector<string> a;
vector<vector<int>> adj;
int dj[4] = {1, 0, -1, 0};
int di[4] = {0, 1, 0, -1};
int pref[MAXN][MAXN];
vector<int> rect = {-1, INF}; // pos i, end j
bool in(int i, int j)
{
if (i >= 0 && i < n && j >= 0 && j < n)
{
return true;
}
return false;
}
int range(int ha, int hb, int j)
{
if (ha > hb)
{
swap(ha, hb);
}
if (ha == 0)
{
return pref[hb][j];
}
return pref[hb][j] - pref[ha - 1][j];
}
signed main()
{
cin >> n >> q;
a.resize(n);
adj.resize(n * n);
for (int i = 0;i < n;i++)
{
cin >> a[i];
}
int cnt = 0;
for (int i = 0;i < n;i++)
{
for (int j = 0;j < n;j++)
{
ind[i][j] = cnt++;
}
}
for (int i = 0;i < n;i++)
{
for (int j = 0; j < n;j++)
{
if (a[i][j] == '#')
{
continue;
}
for (int mi = 0;mi < 4;mi++)
{
for (int mj = 0;mj < 4;mj++)
{
int ni = i + di[mi];
int nj = j + dj[mj];
if (in(ni, nj) && a[ni][nj] == '.')
{
adj[ind[i][j]].pb(ind[ni][nj]);
adj[ind[ni][nj]].pb(ind[i][j]);
}
}
}
}
}
for (int i = 0;i < n;i++)
{
if (a[i][0] == '#')
{
left_wall = true;
}
}
for (int j = 0;j < n;j++)
{
if (a[0][j] == '#')
{
pref[0][j] = 1;
}
else
{
pref[0][j] = 0;
}
}
for (int i = 1;i < n;i++)
{
for (int j = 0;j < n;j++)
{
if (a[i][j] == '#')
{
pref[i][j] = pref[i - 1][j] + 1;
}
else
{
pref[i][j] = pref[i - 1][j];
}
}
}
//cout << "i, j " << rect[0] << " " << rect[1] << '\n';
while (q--)
{
int ia,ja, ib, jb;
cin >> ia >> ja >> ib >> jb;
ia--,ja--,ib--,jb--;
int lo = ja, hi = n - 1, mid = (lo + hi) / 2;
int res = INF;
while (lo < hi)
{
mid = (lo + hi) / 2;
if (range(ia, ib, mid) == 0)
{
hi = mid;
}
else
{
lo = mid + 1;
}
}
if (range(ia, ib, lo) == 0)
{
res = min(res, abs(ja - lo) + abs(jb - lo));
}
lo = 0, hi = ja, mid = (lo + hi + 1) / 2;
while (lo < hi)
{
mid = (lo + hi + 1) / 2;
if (range(ia, ib, mid) == 0)
{
lo = mid;
}
else
{
hi = mid - 1;
}
}
if (range(ia, ib, lo) == 0)
{
res = min(res, abs(ja - lo) + abs(jb - lo));
}
res += abs(ia - ib);
cout << res << '\n';
}
return 0;
}
/*
5 2
.....
##...
##...
#....
.....
*/
/*
5 3
.....
....#
..###
....#
.....
1 5 5 5
2 4 4 4
2 1 3 1
*/Test details
Test 1
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 8 4 ........ ..####.. .##.###. .##.###. ... |
| correct output |
|---|
| 5 0 17 3 |
| user output |
|---|
| 7 6 5 5 |
Feedback: Incorrect character on line 1 col 1: expected "5", got "7"
Test 2
Subtask: 1, 2, 3, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 3 1 ... .#. ... 2 2 2 2 |
| correct output |
|---|
| 0 |
| user output |
|---|
| 2 |
Feedback: Incorrect character on line 1 col 1: expected "0", got "2"
Test 3
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 199 196 ................................. |
| correct output |
|---|
| 468 605 825 532 496 ... |
| user output |
|---|
| 238 201 175 208 254 ... |
Feedback: Incorrect character on line 1 col 1: expected "468", got "238"
Test 4
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 112 347 142 459 239 ... |
| user output |
|---|
| 92 213 176 205 241 ... |
Feedback: Incorrect character on line 1 col 1: expected "112", got "92"
Test 5
Subtask: 1, 3, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 381 544 94 532 98 ... |
| user output |
|---|
| 167 224 68 220 48 ... |
Feedback: Incorrect character on line 1 col 1: expected "381", got "167"
Test 6
Subtask: 1, 2, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 133 73 81 82 53 ... |
| user output |
|---|
| 257 181 255 184 117 ... |
Feedback: Incorrect character on line 1 col 1: expected "133", got "257"
Test 7
Subtask: 1, 2, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 139 52 101 14 144 ... |
| user output |
|---|
| 171 158 231 48 250 ... |
Feedback: Incorrect character on line 1 col 2: expected "139", got "171"
Test 8
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 236 555 878 632 829 ... |
| user output |
|---|
| 240 125 192 290 215 ... |
Feedback: Incorrect character on line 1 col 2: expected "236", got "240"
Test 9
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 425 296 698 577 422 ... |
| user output |
|---|
| 243 216 192 221 158 ... |
Feedback: Incorrect character on line 1 col 1: expected "425", got "243"
Test 10
Subtask: 1, 3, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 1365 7284 11808 6136 9283 ... |
| user output |
|---|
| 185 194 250 228 223 ... |
Feedback: Incorrect character on line 1 col 2: expected "1365", got "185"
Test 11
Subtask: 1, 3, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 6292 17954 16728 8938 1335 ... |
| user output |
|---|
| 70 254 168 176 97 ... |
Feedback: Incorrect character on line 1 col 1: expected "6292", got "70"
Test 12
Subtask: 1, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 27 141 269 127 61 ... |
| user output |
|---|
| 67 105 175 249 149 ... |
Feedback: Incorrect character on line 1 col 1: expected "27", got "67"
Test 13
Subtask: 1, 3, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 19552 19544 19478 19402 19456 ... |
| user output |
|---|
| 374 344 364 360 244 ... |
Feedback: Incorrect character on line 1 col 1: expected "19552", got "374"
Test 14
Subtask: 1, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 17624 17515 17468 17689 17510 ... |
| user output |
|---|
| 366 307 374 307 320 ... |
Feedback: Incorrect character on line 1 col 1: expected "17624", got "366"
Test 15
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 1584 1433 567 2248 1030 ... |
| user output |
|---|
| 258 159 161 60 84 ... |
Feedback: Incorrect character on line 1 col 1: expected "1584", got "258"
Test 16
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 5872 6374 60 323 5311 ... |
| user output |
|---|
| 182 322 108 127 131 ... |
Feedback: Incorrect character on line 1 col 1: expected "5872", got "182"
Test 17
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 1852 213 252 3861 1835 ... |
| user output |
|---|
| 206 299 230 153 265 ... |
Feedback: Incorrect character on line 1 col 1: expected "1852", got "206"
Test 18
Subtask: 1, 5
Verdict: WRONG ANSWER
| input |
|---|
| 200 200 ................................. |
| correct output |
|---|
| 1564 2709 866 1318 1758 ... |
| user output |
|---|
| 98 315 246 234 248 ... |
Feedback: Incorrect character on line 1 col 1: expected "1564", got "98"
Test 19
Subtask: 2, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 997 100000 ................................. |
| correct output |
|---|
| 150 531 370 518 508 ... |
| user output |
|---|
| 1058 567 602 866 1082 ... |
Feedback: Incorrect character on line 1 col 2: expected "150", got "1058"
Test 20
Subtask: 2, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 390 278 783 1269 249 ... |
| user output |
|---|
| 948 896 1183 1411 421 ... |
Feedback: Incorrect character on line 1 col 1: expected "390", got "948"
Test 21
Subtask: 2, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 63 142 813 683 731 ... |
| user output |
|---|
| 571 588 1247 1147 1523 ... |
Feedback: Incorrect character on line 1 col 1: expected "63", got "571"
Test 22
Subtask: 2, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 949 876 1209 494 1033 ... |
| user output |
|---|
| 1083 1060 1429 1016 1109 ... |
Feedback: Incorrect character on line 1 col 1: expected "949", got "1083"
Test 23
Subtask: 3, 5
Verdict: WRONG ANSWER
| input |
|---|
| 997 100000 ................................. |
| correct output |
|---|
| 714 2683 3699 2085 7850 ... |
| user output |
|---|
| 774 547 843 777 508 ... |
Feedback: Incorrect character on line 1 col 2: expected "714", got "774"
Test 24
Subtask: 3, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 5081 1819 1050 4610 528 ... |
| user output |
|---|
| 569 1225 404 996 852 ... |
Feedback: Incorrect character on line 1 col 2: expected "5081", got "569"
Test 25
Subtask: 3, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 3554 6322 6648 2882 1490 ... |
| user output |
|---|
| 1016 442 274 642 478 ... |
Feedback: Incorrect character on line 1 col 1: expected "3554", got "1016"
Test 26
Subtask: 3, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 433976 81646 87810 48080 110879 ... |
| user output |
|---|
| 1056 1688 1196 788 387 ... |
Feedback: Incorrect character on line 1 col 1: expected "433976", got "1056"
Test 27
Subtask: 3, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 207982 140036 208364 51912 56826 ... |
| user output |
|---|
| 608 622 1006 186 996 ... |
Feedback: Incorrect character on line 1 col 1: expected "207982", got "608"
Test 28
Subtask: 3, 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 497525 497563 498000 496804 497335 ... |
| user output |
|---|
| 1827 1741 1524 1896 1291 ... |
Feedback: Incorrect character on line 1 col 1: expected "497525", got "1827"
Test 29
Subtask: 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 38580 2097 9795 38033 1639 ... |
| user output |
|---|
| 1008 763 787 1375 715 ... |
Feedback: Incorrect character on line 1 col 1: expected "38580", got "1008"
Test 30
Subtask: 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 33 20900 25028 1782 13599 ... |
| user output |
|---|
| 537 1310 1216 810 1117 ... |
Feedback: Incorrect character on line 1 col 1: expected "33", got "537"
Test 31
Subtask: 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 1421 1122 1840 834 443 ... |
| user output |
|---|
| 1423 1158 456 558 749 ... |
Feedback: Incorrect character on line 1 col 4: expected "1421", got "1423"
Test 32
Subtask: 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 1378 1751 2274 250 811 ... |
| user output |
|---|
| 1484 1625 1168 1000 1121 ... |
Feedback: Incorrect character on line 1 col 2: expected "1378", got "1484"
Test 33
Subtask: 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 1126 886 544 223 272 ... |
| user output |
|---|
| 1302 974 1108 351 948 ... |
Feedback: Incorrect character on line 1 col 2: expected "1126", got "1302"
Test 34
Subtask: 4, 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 327286 447779 447534 448307 446997 ... |
| user output |
|---|
| 1212 1315 1588 1827 1919 ... |
Feedback: Incorrect character on line 1 col 1: expected "327286", got "1212"
Test 35
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 2597 1473 1933 2691 1837 ... |
| user output |
|---|
| 1047 771 879 1343 1039 ... |
Feedback: Incorrect character on line 1 col 1: expected "2597", got "1047"
Test 36
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 553 4357 3147 6951 1573 ... |
| user output |
|---|
| 541 935 1083 1527 451 ... |
Feedback: Incorrect character on line 1 col 2: expected "553", got "541"
Test 37
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 1723 2039 1871 5638 4256 ... |
| user output |
|---|
| 1039 1563 1203 668 1048 ... |
Feedback: Incorrect character on line 1 col 2: expected "1723", got "1039"
Test 38
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 1546 704 2796 3802 1870 ... |
| user output |
|---|
| 1248 1150 628 1366 586 ... |
Feedback: Incorrect character on line 1 col 2: expected "1546", got "1248"
Test 39
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 3115 2042 2083 3227 740 ... |
| user output |
|---|
| 1307 516 891 1791 618 ... |
Feedback: Incorrect character on line 1 col 1: expected "3115", got "1307"
Test 40
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 5222 3211 5230 1772 2310 ... |
| user output |
|---|
| 1176 1283 1198 838 1176 ... |
Feedback: Incorrect character on line 1 col 1: expected "5222", got "1176"
Test 41
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 159214 68851 200821 141404 145704 ... |
| user output |
|---|
| 1328 889 1101 896 1230 ... |
Feedback: Incorrect character on line 1 col 2: expected "159214", got "1328"
Test 42
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 1843 25028 124430 84542 131339 ... |
| user output |
|---|
| 173 1052 860 1100 925 ... |
Feedback: Incorrect character on line 1 col 2: expected "1843", got "173"
Test 43
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 111206 75799 12026 142133 20483 ... |
| user output |
|---|
| 976 679 500 973 369 ... |
Feedback: Incorrect character on line 1 col 1: expected "111206", got "976"
Test 44
Subtask: 5
Verdict: WRONG ANSWER
| input |
|---|
| 1000 100000 ................................. |
| correct output |
|---|
| 20360 9075 12187 54923 54574 ... |
| user output |
|---|
| 480 285 363 1551 1172 ... |
Feedback: Incorrect character on line 1 col 1: expected "20360", got "480"