— Dark mode

Datatähti 2026 alku

Hypyt

  • Start: 2025-10-27 00:00:00
  • End: 2025-11-10 00:00:00
Submission details
Task:Hypyt
Sender:Luhpossu
Submission time:2025-10-30 11:39:41 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#20.01 s1, 2, 3, 4, 5details
#3ACCEPTED0.00 s1, 2, 3, 4, 5details
#40.00 s1, 2, 3, 4, 5details
#5ACCEPTED0.00 s1, 2, 3, 4, 5details
#6--2, 5details
#7--2, 5details
#8--2, 5details
#9--3, 4, 5details
#10--3, 4, 5details
#11--3, 4, 5details
#12--4, 5details
#13--4, 5details
#14--4, 5details
#15--5details
#16--5details
#17--5details
#18--5details
#19--5details
#20--5details
#21--5details
#22ACCEPTED0.00 s1, 2, 3, 4, 5details
#23ACCEPTED0.00 s1, 2, 3, 4, 5details
#24--5details
#25--5details
#26--5details
#27ACCEPTED0.50 s5details

Code

#include <algorithm>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <memory>
#include <vector>
 
using pi = std::pair<int, int>;
static int max;
// static std::vector<pi> checked;
 
std::vector<std::shared_ptr<std::vector<pi>>> rows;
std::vector<std::shared_ptr<std::vector<pi>>> columns;

std::vector<std::shared_ptr<std::vector<std::pair<pi, int>>>> revRows;
std::vector<std::shared_ptr<std::vector<std::pair<pi, int>>>> revColumns;
 
constexpr int NOT_FOUND = 100000;
int tries = 0;
 
void findPath(std::deque<pi> path, pi target) {
    pi pos = path.back();
 
    std::vector<pi> row = *rows[pos.second];
    std::vector<pi> column = *columns[pos.first];

    // std::shared_ptr<std::vector<std::pair<pi, int>>> revRow = revRows[pos.second];
    // std::shared_ptr<std::vector<std::pair<pi, int>>> revColumn = revColumns[pos.first];

    if (static_cast<int>(path.size() - 1) >= max) return;
    if (--tries <= 0) return;

    if (target.first == pos.first && target.second == pos.second) {
        max = path.size() - 1;
        
        return;
    }

    std::vector<std::pair<bool, pi>> positions;

    for (auto i : row) positions.push_back({false, i});
    for (auto i : column) positions.push_back({true, i});

    std::sort(positions.begin(), positions.end(), [target](std::pair<bool, pi> i1, std::pair<bool, pi> i2){
        return 
        (std::abs(i1.second.second - target.second) + 1) * (std::abs(i1.second.first - target.first) + 1) < 
        (std::abs(i2.second.second - target.second) + 1) * (std::abs(i2.second.first - target.first) + 1);
    });

    for (auto [col, pos2] : positions) {
        bool guh = false;
        for (auto j : path) {
            if (j == pos2) {
                guh = true;
                break;
            }
        }
        if (guh) continue;
 
        std::deque<pi> path2 = path;
        path2.push_back(pos2);
 
        findPath(path2, target);
    }
}
//
// void reverse(std::deque<pi> path, int length) {
//     pi pos = path.back();
//
//     std::shared_ptr<std::vector<pi>> row = rows[pos.second];
//     std::shared_ptr<std::vector<pi>> column = columns[pos.first];
//
//     std::shared_ptr<std::vector<std::pair<pi, int>>> revRow = revRows[pos.second];
//     std::shared_ptr<std::vector<std::pair<pi, int>>> revColumn = revColumns[pos.first];
//
//     int steps = static_cast<int>(path.size());
//     for (std::size_t i = 0; i < revRow->size(); i++) {
//         auto guh = revRow->at(i);
//
//         if (guh.second > steps) 
//     }
//
//     for (auto pair : *revColumn) {
//
//     }
//
//     if (static_cast<int>(path.size()) > length) return;
//
//     for (std::size_t i = 0; i < row->size(); i++) {
//         pi pos2 = row->at(i);
//
//         bool guh = false;
//         for (auto j : path) {
//             if (j == pos2) {
//                 guh = true;
//                 break;
//             }
//         }
//         if (guh) continue;
//
//         std::deque<pi> path2 = path;
//         path2.push_back(pos2);
//
//         findPath(path2, target);
//     }
//
//     for (std::size_t i = 0; i < column->size(); i++) {
//         pi pos2 = column->at(i);
//
//         bool guh = false;
//         for (auto j : path) {
//             if (j == pos2) {
//                 guh = true;
//                 break;
//             }
//         }
//         if (guh) continue;
//
//         std::deque<pi> path2 = path;
//         path2.push_back(pos2);
//
//         findPath(path2, target);
//     }
// }
 
int main([[maybe_unused]] int argc, [[maybe_unused]] char *argv[]) {
    int width, height, count; std::cin >> height >> width >> count;
 
 
    for (int i = 0; i < height; i++) rows.push_back(std::make_shared<std::vector<pi>>());
    for (int i = 0; i < width; i++) columns.push_back(std::make_shared<std::vector<pi>>());
 
    for (int i = 0; i < height; i++) {
        char c;
 
        for (int j = 0; j < width; j++) {
            std::cin >> c;
            if (c != '.') continue;
 
            pi pos { j, i };
 
            columns.at(j)->push_back(pos);
            rows.at(i)->push_back(pos);
        }
    }
 
    std::vector<int> answers;
    for (int i = 0; i < count; i++) {
        int y1, x1, y2, x2; std::cin >> y1 >> x1 >> y2 >> x2;
 
        max = NOT_FOUND;
        tries = 100;
        findPath({{x1 - 1, y1 - 1}}, {x2 - 1, y2 - 1});
        if (max == NOT_FOUND) max = -1;
        answers.push_back(max);
    }
 
    for (auto i : answers) std::cout << i << std::endl;
}


// #include <iostream>
// #include <memory>
// #include <vector>
//
// int main(int argc, char *argv[]) {
//     int height, width, count; std::cin >> height >> width >> count;
//
//     std::vector<bool*> rows;
//     for (int y = 0; y < height; y++) {
//         auto row = new bool[width];
//
//         for (int x = 0; x < width; x++) {
//             char c; std::cin >> c;
//             row[x] = (c == '.');
//         }
//
//         rows.push_back(row);
//     }
//
//
// }

Test details

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
4 6 5
.*.***
*...**
*****.
*..*.*
...
view save

correct output
1
0
3
3
-1
view save

user output
1
0
3
3
-1
view save

Test 2

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
..........
.....*....
........*.
*.*....*..
...
view save

correct output
1
2
1
2
2
...
view save

user output
1
2
1
2
2
...
view save

Feedback: Incorrect character on line 8 col 1: expected "2", got "4"

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
10 10 10
*...***.**
*****.*...
**..**.**.
..**.**.*.
...
view save

correct output
1
2
2
1
2
...
view save

user output
1
2
2
1
2
...
view save

Test 4

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
***.*.****
**********
*.********
.*.***.**.
...
view save

correct output
3
4
2
3
4
...
view save

user output
3
4
2
3
4
...
view save

Feedback: Incorrect character on line 6 col 1: expected "2", got "6"

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
10 10 1
.****.****
**.**..***
**********
*******..*
...
view save

correct output
7
view save

user output
7
view save

Test 6

Group: 2, 5

Verdict:

input
250 250 250
.*...*.....*******..**...*.......
view save

correct output
2
3
3
2
2
...
view save

user output
(empty)

Test 7

Group: 2, 5

Verdict:

input
250 250 250
...*......**.**.*.*..**..*..**...
view save

correct output
2
2
2
2
3
...
view save

user output
(empty)

Test 8

Group: 2, 5

Verdict:

input
250 250 250
**..**..****.****.*.***.***..*...
view save

correct output
2
3
3
3
3
...
view save

user output
(empty)

Test 9

Group: 3, 4, 5

Verdict:

input
40 40 200000
...*.**.*..*.............*.*.....
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 10

Group: 3, 4, 5

Verdict:

input
40 40 200000
**.**..*.*.*.******....****.*....
view save

correct output
2
1
3
2
2
...
view save

user output
(empty)

Test 11

Group: 3, 4, 5

Verdict:

input
40 40 200000
.*.*.**.*****.***.*.****.**.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 12

Group: 4, 5

Verdict:

input
80 80 200000
*....**.***..****...*.....*......
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 13

Group: 4, 5

Verdict:

input
80 80 200000
.***.*..*.***..*****....**...*...
view save

correct output
3
2
2
3
2
...
view save

user output
(empty)

Test 14

Group: 4, 5

Verdict:

input
80 80 200000
*******.*****.*..*..****...***...
view save

correct output
2
3
1
2
2
...
view save

user output
(empty)

Test 15

Group: 5

Verdict:

input
250 250 200000
*....*..*..*..**..*.........**...
view save

correct output
3
2
2
2
2
...
view save

user output
(empty)

Test 16

Group: 5

Verdict:

input
250 250 200000
..*....*..*......*.**.*.*..***...
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 17

Group: 5

Verdict:

input
250 250 200000
*..*.*****.*********.****.****...
view save

correct output
3
3
2
2
2
...
view save

user output
(empty)

Test 18

Group: 5

Verdict:

input
250 250 200000
*********.**********.******.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 19

Group: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
104
422
145
93
65
...
view save

user output
(empty)

Test 20

Group: 5

Verdict:

input
250 250 200000
..****************************...
view save

correct output
57
155
38
65
98
...
view save

user output
(empty)

Test 21

Group: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
498
498
498
498
498
...
view save

user output
(empty)

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
10 1 10
*
*
.
*
...
view save

correct output
0
1
1
0
0
...
view save

user output
0
1
1
0
0
...
view save

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
1 10 10
........*.
1 7 1 10
1 4 1 7
1 5 1 1
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Test 24

Group: 5

Verdict:

input
250 1 200000
*
.
*
.
...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 25

Group: 5

Verdict:

input
1 250 200000
*.*.*...*.*.**.***..**.*.*..**...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 26

Group: 5

Verdict:

input
250 250 200000
.................................
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 27

Group: 5

Verdict: ACCEPTED

input
250 250 200000
******************************...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Tasks

A Palindromi-B Monikulmio-C Tulkki-D Maalaus-E Hypyt-F Lukujono-

Submissions (Luhpossu)

2025-11-06 22:55:01 602025-11-06 22:54:36 2025-11-06 22:29:06 602025-11-06 22:04:50 602025-11-06 22:01:13 602025-11-06 12:49:07 602025-11-06 12:48:44 602025-11-06 09:32:48 602025-11-06 09:32:35 602025-11-06 09:32:19 602025-11-06 09:30:43 602025-11-06 09:22:07 02025-11-06 09:19:38 602025-11-06 09:16:34 602025-11-06 09:15:35 02025-11-06 09:04:32 602025-11-06 08:23:03 602025-11-06 08:05:14 602025-11-06 07:51:40 602025-11-05 23:28:38 02025-11-05 23:28:20 02025-11-05 23:27:52 02025-11-05 23:27:24 02025-11-05 22:57:15 02025-11-05 20:38:42 02025-11-05 20:24:28 02025-11-04 13:50:35 02025-11-04 13:24:25 452025-11-04 11:03:51 602025-11-04 11:03:29 302025-11-04 11:03:07 602025-11-04 10:59:59 302025-11-04 10:57:37 602025-11-04 10:55:28 02025-11-03 23:33:56 402025-11-03 23:33:15 402025-11-03 23:32:21 102025-11-03 23:31:59 02025-11-03 23:29:27 602025-11-03 23:29:00 602025-11-03 23:25:35 602025-11-03 22:51:29 602025-11-03 22:51:11 2025-11-03 22:47:04 602025-11-03 22:45:37 602025-11-03 21:21:05 602025-11-03 21:20:11 02025-11-03 21:19:31 02025-11-03 21:18:50 02025-11-03 20:41:28 02025-11-03 20:17:10 602025-11-03 20:17:00 2025-11-03 20:08:45 602025-11-03 20:08:29 2025-11-03 20:04:12 02025-11-03 20:03:02 02025-11-03 20:02:19 02025-11-03 20:01:27 02025-11-03 19:39:29 02025-11-02 16:35:57 302025-11-02 16:35:37 602025-11-02 16:31:13 302025-11-02 16:30:12 102025-11-02 16:08:00 302025-11-02 16:07:32 02025-11-02 16:06:59 302025-11-02 16:06:27 102025-11-02 16:05:53 02025-11-02 16:05:17 02025-11-02 15:54:32 02025-11-02 15:54:08 02025-11-02 15:14:38 02025-11-02 15:14:13 02025-11-02 15:07:23 602025-11-02 15:06:52 02025-11-02 15:01:12 302025-11-02 14:50:03 602025-11-02 14:49:05 102025-11-02 14:48:22 602025-11-02 14:47:00 602025-11-02 14:46:42 2025-11-02 14:45:44 302025-11-02 02:44:39 302025-11-02 02:43:49 302025-11-02 02:37:32 02025-11-02 02:20:38 02025-11-02 02:20:13 602025-11-02 02:19:49 02025-11-02 02:13:34 602025-11-02 02:12:58 602025-11-02 02:12:29 602025-11-02 02:12:07 02025-11-02 02:10:22 602025-11-02 02:09:59 02025-11-02 02:09:19 02025-11-02 02:08:53 02025-11-02 01:51:23 102025-11-02 01:50:56 02025-11-02 01:50:40 02025-11-02 01:38:19 02025-11-01 23:13:33 02025-11-01 23:12:20 02025-11-01 23:11:53 02025-11-01 23:10:45 302025-11-01 23:10:28 2025-11-01 23:09:21 02025-11-01 23:08:57 02025-11-01 23:08:14 02025-11-01 23:04:07 02025-11-01 23:02:46 02025-11-01 23:01:19 02025-11-01 23:00:49 02025-11-01 22:58:38 02025-11-01 22:57:56 02025-11-01 18:37:19 02025-11-01 18:33:05 02025-11-01 14:41:07 302025-11-01 14:40:42 302025-11-01 14:40:05 2025-11-01 14:34:16 302025-11-01 14:25:16 02025-11-01 02:08:39 302025-11-01 02:03:18 302025-11-01 02:02:48 02025-11-01 01:49:21 302025-11-01 01:46:57 302025-11-01 01:46:35 2025-10-31 20:14:54 302025-10-31 20:09:45 302025-10-31 20:00:45 302025-10-31 19:55:15 02025-10-31 19:42:40 302025-10-31 19:38:42 02025-10-31 19:25:08 302025-10-31 18:47:22 302025-10-31 18:46:09 302025-10-31 18:45:16 2025-10-31 17:49:17 302025-10-31 17:46:22 302025-10-31 17:16:20 302025-10-31 17:03:30 302025-10-31 17:00:19 302025-10-31 16:56:08 302025-10-31 16:55:37 2025-10-31 16:33:56 302025-10-31 16:19:09 02025-10-31 16:18:19 02025-10-31 16:11:56 02025-10-31 13:57:56 102025-10-31 13:49:28 02025-10-30 11:39:41 02025-10-30 11:39:23 102025-10-30 11:39:05 102025-10-30 11:38:40 102025-10-30 11:37:15 102025-10-30 11:35:59 02025-10-30 11:35:27 02025-10-30 11:06:11 02025-10-30 11:05:38 02025-10-30 10:24:18 102025-10-30 09:22:18 102025-10-30 09:21:23 02025-10-30 09:20:35 02025-10-29 17:41:35 02025-10-29 17:37:38 0