— Dark mode

Datatähti 2024 alku

Käännöt

  • Start: 2023-10-30 00:00:00
  • End: 2023-11-13 00:00:00
CSES - Datatähti 2024 alku - Results
Submission details
Task:Käännöt
Sender:chaotic
Submission time:2023-11-11 18:21:08 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#10.00 s1details
#20.00 s1details
#30.00 s1details
#40.00 s1details
#50.00 s1details
#60.00 s2details
#70.00 s2details
#80.00 s2details
#90.00 s2details
#100.00 s2details
#110.00 s2details
#120.00 s2details
#130.00 s2details
#140.00 s2details
#150.00 s2details
#160.00 s2details
#170.00 s3details
#180.00 s3details
#190.00 s3details
#200.00 s3details
#210.00 s3details
#220.00 s3details
#230.00 s3details
#240.00 s3details
#250.00 s3details
#260.00 s4details
#270.00 s4details
#280.00 s4details
#290.00 s4details
#300.00 s4details
#310.00 s4details
#320.00 s4details
#330.00 s4details
#340.00 s4details

Code

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <ranges>
#include <sstream>
#include <string>
#include <vector>

auto sort_2(std::vector<int>& values) {
    std::vector<size_t> operations;
    operations.reserve(100000);

    // Swaps idx and idx+1
    auto swap = [&](size_t idx) {
        std::swap(values[idx], values[idx + 1]);
        operations.push_back(idx);
    };

    size_t remaining = values.size();

    while (remaining != 0) {
        size_t idx =
            std::ranges::find(values | std::views::take(remaining), remaining) - values.begin();

        for (; idx != remaining - 1; ++idx) { swap(idx); }
        --remaining;
    }

    return std::tuple(true, operations);
}

std::tuple<bool, std::vector<size_t>> sort_3(std::vector<int>& values) {
    // Check
    // values[i] % 2 should be 1
    for (size_t i = 0; i < values.size(); ++i) {
        if ((values[i] - i) % 2 != 1) return {false, {}};
    }

    std::vector<size_t> operations;
    operations.reserve(100000);

    // Swaps idx and idx+2
    auto swap = [&](size_t idx) {
        std::swap(values[idx], values[idx + 2]);
        operations.push_back(idx);
    };

    size_t remaining = values.size();

    while (remaining != 0) {
        size_t idx =
            std::ranges::find(values | std::views::take(remaining), remaining) - values.begin();

        for (; idx != remaining - 1; idx += 2) { swap(idx); }
        --remaining;
    }

    return {true, operations};
}

struct op_4 {
    size_t min_list_len;
    std::vector<size_t> indices;
};
inline constexpr size_t unsortable = -1;

// There are 24 4-long lists
inline std::map<std::array<int, 4>, op_4> const sort_4_map = {
    {{1, 2, 3, 4}, {4, {}}                         },
    {{1, 2, 4, 3}, {unsortable, {}}                },
    {{1, 3, 2, 4}, {unsortable, {}}                },
    {{1, 3, 4, 2}, {6, {0, 2, 1, 2, 1, 0, 2, 0, 1}}},
    {{1, 4, 2, 3}, {6, {0, 2, 1, 0, 1, 0, 1, 2, 1}}},
    {{1, 4, 3, 2}, {unsortable, {}}                },
    {{2, 1, 3, 4}, {unsortable, {}}                },
    {{2, 1, 4, 3}, {6, {2, 1, 2, 0, 2, 1, 2}}      },
    {{2, 3, 1, 4}, {6, {1, 2, 1, 2, 0, 1, 0, 2}}   },
    {{2, 3, 4, 1}, {unsortable, {}}                },
    {{2, 4, 1, 3}, {unsortable, {}}                },
    {{2, 4, 3, 1}, {6, {2, 1, 2, 1, 0, 2, 0, 1}}   },
    {{3, 1, 2, 4}, {6, {2, 0, 1, 0, 2, 1, 2, 1}}   },
    {{3, 1, 4, 2}, {unsortable, {}}                },
    {{3, 2, 1, 4}, {unsortable, {}}                },
    {{3, 2, 4, 1}, {6, {2, 0, 1, 0, 1, 0, 2, 1}}   },
    {{3, 4, 1, 2}, {6, {2, 1, 0, 2, 0, 1, 2, 0}}   },
    {{3, 4, 2, 1}, {unsortable, {}}                },
    {{4, 1, 2, 3}, {unsortable, {}}                },
    {{4, 1, 3, 2}, {6, {1, 2, 0, 1, 2, 1, 2, 1}}   },
    {{4, 2, 1, 3}, {6, {1, 2, 1, 0, 1, 0, 1, 2}}   },
    {{4, 2, 3, 1}, {unsortable, {}}                },
    {{4, 3, 1, 2}, {unsortable, {}}                },
    {{4, 3, 2, 1}, {4, {0}}                        },
};

std::tuple<bool, std::vector<size_t>> sort_4(std::vector<int>& values) {
    // First sort the list except first 4 elements
    std::vector<size_t> operations;
    operations.reserve(100000);

    // Swaps idx and idx+2
    auto swap = [&](size_t idx) {
        std::swap(values[idx], values[idx + 3]);
        std::swap(values[idx + 1], values[idx + 2]);
        operations.push_back(idx);
    };

    size_t value = values.size();

    for (; value != 4; --value) {
        size_t idx = std::ranges::find(values | std::views::take(value), value) - values.begin();

        // Move this one to the back
        int distance = value - (idx + 1);
        assert(distance >= 0);
        if (distance == 0) continue;

        // Align distance to 0 mod 3
        // Afterwards idx = pos o felement
        switch (distance % 3) {
        case 1: {
            if (distance != 1) {
                swap(idx);
                idx += 3;
            }
            swap(idx - 2);
            swap(idx - 3);
            idx -= 2;
            break;
        }
        case 2: {
            if (distance != 2) {
                swap(idx);
                idx += 3;
            }
            swap(idx - 2);
            idx -= 1;
            break;
        }
        }

        distance = value - (idx + 1);
        assert(distance % 3 == 0);

        // Move by multiplies of 3
        int times = distance / 3;
        for (int i = 0; i < times; ++i) {
            swap(idx);
            idx += 3;
        }
        assert(values[value - 1] == int(value));
    }

    // Sort first 4 elements
    std::array<int, 4> first4 = {values[0], values[1], values[2], values[3]};
    auto& info                = sort_4_map.at(first4);

    if (info.min_list_len > values.size()) { return {false, {}}; }
    operations.insert(operations.end(), info.indices.begin(), info.indices.end());

    return {true, operations};
}

using op_5 = op_4;

std::map<std::array<int, 5>, op_5> sort_5_map = {
    {{1, 2, 3, 4, 5, }, {5 , {}}},
    {{1, 4, 5, 2, 3, }, {7 , {1, 2, 0, 2, 0, }}},
    {{3, 2, 5, 4, 1, }, {7 , {2, 0, 2, 1, }}},
    {{3, 4, 1, 2, 5, }, {7 , {0, 1, 2, 0, 2, }}},
    {{5, 2, 1, 4, 3, }, {7 , {1, 2, 0, 2, }}},
    {{5, 4, 3, 2, 1, }, {5 , {0, }}},

    };

std::tuple<bool, std::vector<size_t>> sort_5(std::vector<int>& values) {
    for (size_t i = 0; i < values.size(); ++i) {
        if ((values[i] - i) % 2 != 1) return {false, {}};
    }

    // First sort the list except first 4 elements
    std::vector<size_t> operations;
    operations.reserve(100000);

    // Swaps idx and idx+2
    auto swap = [&](size_t idx) {
        std::swap(values[idx], values[idx + 4]);
        std::swap(values[idx + 1], values[idx + 3]);
        operations.push_back(idx);
    };

    size_t value = values.size();
    for (; value != 5; --value) {
        size_t idx = std::ranges::find(values | std::views::take(value), value) - values.begin();

        int distance = value - (idx + 1);
        assert(distance >= 0);
        if (distance == 0) continue;

        // Align to a multiple of 4
        // 1 and 3 are impossible and should be already checked
        switch (distance % 4) {
        case 1: assert(false);
        case 2: {
            if (distance != 2) {
                swap(idx);
                idx += 4;
            }
            swap(idx - 3);
            idx -= 2;
            break;
        }
        case 3: assert(false);
        }

        distance = value - (idx + 1);
        assert(distance % 4 == 0);

        int times = distance / 4;
        for (int i = 0; i < times; ++i) {
            swap(idx);
            idx += 4;
        }
    }

    // Sort first 5 elements
    std::array<int, 5> first5 = {values[0], values[1], values[2], values[3], values[4]};
    auto it = sort_5_map.find(first5);
    if (it == sort_5_map.end()) { return {false, {}}; }
    auto& info                = it->second;

    operations.insert(operations.end(), info.indices.begin(), info.indices.end());

    return {true, operations};
}

int main() {
    std::istringstream input(R"(10 5
5 2 3 4 1 6 7 10 9 8 )");
    //    auto& input = std::cin;

    size_t len;
    int k;
    input >> len >> k;

    std::vector<int> values;
    values.reserve(len);
    for (size_t i = 0; i < len; ++i) {
        int n;
        input >> n;
        values.push_back(n);
    }

    std::tuple<bool, std::vector<size_t>> res;
    switch (k) {
    case 2: res = sort_2(values); break;
    case 3: res = sort_3(values); break;
    case 4: {
        res = sort_4(values);
        //        for (auto x: values) std::cout << x << ", ";
        //        std::cout << "\n";
        break;
    }
    case 5: {
        res = sort_5(values);
//        for (auto x: values) std::cout << x << ", ";
//        std::cout << "\n";
        break;
    }
    }

    auto& [possible, vec] = res;

    if (!possible) {
        std::cout << "NO\n";
        return 0;
    } else {
        std::cout << "YES\n";
        std::cout << vec.size() << "\n";
        for (auto const& val: vec) { std::cout << val + 1 << ' '; }
        std::cout << "\n";
    }
}

Test details

Test 1

Group: 1

Verdict:

input
5 2
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 2

Group: 1

Verdict:

input
5 2
2 1 3 4 5
view save

correct output
YES
1
1
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 3

Group: 1

Verdict:

input
20 2
6 20 18 2 16 13 19 17 8 14 11 ...
view save

correct output
YES
366
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 4

Group: 1

Verdict:

input
100 2
100 92 62 88 12 7 43 31 19 72 ...
view save

correct output
YES
2876
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 5

Group: 1

Verdict:

input
100 2
100 99 98 97 96 95 94 93 92 91...
view save

correct output
YES
5248
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 6

Group: 2

Verdict:

input
5 3
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 7

Group: 2

Verdict:

input
5 3
3 5 4 1 2
view save

correct output
NO
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 8

Group: 2

Verdict:

input
5 3
5 2 1 4 3
view save

correct output
YES
8
1 2 1 3 1 2 3 1
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 9

Group: 2

Verdict:

input
20 3
19 14 1 18 3 4 11 20 13 6 17 8...
view save

correct output
YES
52
8 10 12 14 16 18 1 3 5 7 9 11 ...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 10

Group: 2

Verdict:

input
20 3
9 6 13 18 5 10 3 2 7 20 1 4 19...
view save

correct output
YES
50
10 12 14 16 18 13 15 17 4 6 8 ...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 11

Group: 2

Verdict:

input
500 3
53 52 21 76 25 142 5 4 83 176 ...
view save

correct output
YES
15194
334 336 338 340 342 344 346 34...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 12

Group: 2

Verdict:

input
500 3
51 44 147 172 1 28 27 82 233 1...
view save

correct output
YES
15565
366 368 370 372 374 376 378 38...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 13

Group: 2

Verdict:

input
500 3
75 46 179 62 221 14 67 154 89 ...
view save

correct output
YES
15920
454 456 458 460 462 464 466 46...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 14

Group: 2

Verdict:

input
500 3
161 54 285 12 71 142 111 94 97...
view save

correct output
YES
15931
408 410 412 414 416 418 420 42...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 15

Group: 2

Verdict:

input
500 3
122 260 455 113 315 276 433 43...
view save

correct output
NO
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 16

Group: 2

Verdict:

input
500 3
499 500 497 498 495 496 493 49...
view save

correct output
YES
62264
2 4 6 8 10 12 14 16 18 20 22 2...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 17

Group: 3

Verdict:

input
5 4
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 18

Group: 3

Verdict:

input
5 4
5 1 2 3 4
view save

correct output
YES
4
1 2 1 2
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 19

Group: 3

Verdict:

input
500 4
58 14 107 124 4 113 24 290 56 ...
view save

correct output
YES
15698
389 392 395 398 401 404 407 41...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 20

Group: 3

Verdict:

input
500 4
113 187 278 242 23 67 48 298 3...
view save

correct output
YES
15004
480 481 480 482 485 488 491 49...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 21

Group: 3

Verdict:

input
500 4
5 233 199 35 213 354 11 134 30...
view save

correct output
YES
16770
458 461 464 467 470 473 476 47...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 22

Group: 3

Verdict:

input
500 4
169 47 21 137 57 138 360 147 4...
view save

correct output
YES
15889
497 371 372 371 373 376 379 38...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 23

Group: 3

Verdict:

input
500 4
493 409 291 313 156 443 496 40...
view save

correct output
YES
22886
480 481 480 482 485 488 491 49...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 24

Group: 3

Verdict:

input
500 4
137 99 100 226 326 298 140 340...
view save

correct output
NO
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 25

Group: 3

Verdict:

input
500 4
500 499 498 497 496 495 494 49...
view save

correct output
YES
41458
1 2 1 2 5 8 11 14 17 20 23 26 ...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 26

Group: 4

Verdict:

input
5 5
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 27

Group: 4

Verdict:

input
5 5
5 4 3 2 1
view save

correct output
YES
1
1
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 28

Group: 4

Verdict:

input
500 5
145 26 285 154 147 314 141 40 ...
view save

correct output
YES
13786
216 220 224 228 232 236 240 24...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 29

Group: 4

Verdict:

input
500 5
137 22 399 292 249 6 51 224 42...
view save

correct output
YES
13465
456 460 464 468 472 476 480 48...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 30

Group: 4

Verdict:

input
500 5
153 52 85 100 329 60 433 468 4...
view save

correct output
YES
13642
377 378 377 380 384 388 392 39...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 31

Group: 4

Verdict:

input
500 5
267 326 95 108 189 32 291 366 ...
view save

correct output
YES
14639
213 214 213 216 220 224 228 23...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 32

Group: 4

Verdict:

input
500 5
15 450 272 80 321 101 247 438 ...
view save

correct output
NO
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 33

Group: 4

Verdict:

input
499 5
497 498 499 496 495 494 493 49...
view save

correct output
YES
30886
3 7 11 15 19 23 27 31 35 39 43...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Test 34

Group: 4

Verdict:

input
500 5
499 500 497 498 495 496 493 49...
view save

correct output
YES
30919
1 4 8 12 16 20 24 28 32 36 40 ...
view save

user output
YES
7
5 6 5 2 3 2 1 
view save

Tasks

A Lumimyrsky-B Monistus-C Laskettelukeskus-D Uolevin kalansaalis-E Käännöt-F Säähavainnot-

Submissions (chaotic)

2023-11-11 18:21:51 1002023-11-11 18:21:08 02023-11-09 18:21:30 652023-11-08 23:59:11 322023-11-08 23:51:41 132023-11-08 23:47:24 0