oj.uz

Submission #679797

# Submission time Handle Problem Language Result Execution time Memory
679797 2023-01-09T08:49:33 Z bashkort Monster Game (JOI21_monster) C++17
89 / 100
 141 ms 1896 KB 
#include <bits/stdc++.h>
#include "monster.h"

using namespace std;

mt19937 rnd(228);

vector<int> Solve(int n) {
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);

    shuffle(ord.begin(), ord.end(), rnd);

    map<pair<int, int>, bool> asked;
    auto ask = [&](int i, int j) {
        if (!asked.count({i, j})) {
            asked[{i, j}] = Query(i, j);
            asked[{j, i}] = !asked[{i, j}];
        }
        return asked[{i, j}];
    };

    stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
        return !ask(i, j);
    });

//    auto merge_sort = [&](auto self, vector<int> a) -> vector<int> {
//        if (a.size() == 1) {
//            return a;
//        }
//        int mid = a.size() / 2;
//        auto L = self(self, vector(a.begin(), a.begin() + mid));
//        auto R = self(self, vector(a.begin() + mid, a.end()));
//        a.clear();
//        int i = 0, j = 0;
//        while (i < L.size() || j < R.size()) {
//            if (i < L.size() && (j == R.size() || !ask(L[i], R[j]))) {
//                a.push_back(L[i++]);
//            } else {
//                a.push_back(R[j++]);
//            }
//        }
//        return a;
//    };
//
//    ord = merge_sort(merge_sort, ord);

    auto is_n = [&](int i) {
        int killer = -1;
        int skipped = 0;
        for (int k = 0; k < n && skipped < 2; ++k) {
            if (k == i) continue;
            if (ask(ord[i], ord[k])) {
            } else {
                ++skipped;
                killer = k;
            }
        }
        if (skipped == 1) {
            int kek = 0;
            skipped = 0;
            for (int k = 0; k < i && skipped < 2; ++k) {
                if (k == i) continue;
                if (k != killer) {
                    bool now = ask(ord[killer], ord[k]);
                    if (!now) {
                        skipped += 1;
                    }
                }
            }
            if (skipped == 1) {
                return true;
            }
        }
        return false;
    };

    bool damn = false;

    for (int i = n - 1; i > 0;) {
        if (i == n - 1) {
            if (is_n(i)) {
                --i;
                continue;
            }
        }
        if (damn || i + 1 < n && ask(ord[i], ord[i + 1])) {
            --i;
            damn = false;
            continue;
        }
        damn = false;
        int j = i - 2;
        while (j >= 0 && ask(ord[j], ord[i])) {
            --j;
        }
        if (i - j > 3 && ask(ord[i - 1], ord[j + 1])) {
            ++j;
            damn = true;
        } else if (i - j == 3) {
            if (i == n - 1) {
                if (is_n(i - 1)) {
                    swap(ord[i], ord[i - 1]);
                } else {
                    swap(ord[i - 2], ord[i]);
                }
            } else {
                if (ask(ord[i - 1], ord[i + 1])) {
                    swap(ord[i], ord[i - 1]);
                } else {
                    swap(ord[i - 2], ord[i]);
                }
            }
            i -= 3;
            continue;
        }
        reverse(ord.begin() + j + 1, ord.begin() + i + 1);
        i = j;
    }

    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[ord[i]] = i;
    }


    return ans;
}

Compilation message

monster.cpp: In lambda function:
monster.cpp:60:17: warning: unused variable 'kek' [-Wunused-variable]
   60 |             int kek = 0;
      |                 ^~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:87:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   87 |         if (damn || i + 1 < n && ask(ord[i], ord[i + 1])) {
      |                     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 21 ms 456 KB Output is correct
17 Correct 16 ms 564 KB Output is correct
18 Correct 14 ms 456 KB Output is correct
19 Correct 15 ms 420 KB Output is correct
20 Correct 14 ms 408 KB Output is correct
21 Correct 0 ms 296 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 1 ms 208 KB Output is correct
24 Correct 1 ms 208 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 20 ms 460 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 1 ms 208 KB Output is correct
30 Correct 1 ms 208 KB Output is correct
31 Correct 1 ms 208 KB Output is correct
32 Correct 20 ms 396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 21 ms 456 KB Output is correct
17 Correct 16 ms 564 KB Output is correct
18 Correct 14 ms 456 KB Output is correct
19 Correct 15 ms 420 KB Output is correct
20 Correct 14 ms 408 KB Output is correct
21 Correct 0 ms 296 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 1 ms 208 KB Output is correct
24 Correct 1 ms 208 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 20 ms 460 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 1 ms 208 KB Output is correct
30 Correct 1 ms 208 KB Output is correct
31 Correct 1 ms 208 KB Output is correct
32 Correct 20 ms 396 KB Output is correct
33 Correct 107 ms 1896 KB Output is correct
34 Correct 95 ms 1736 KB Output is correct
35 Correct 125 ms 1716 KB Output is correct
36 Correct 95 ms 1892 KB Output is correct
37 Correct 121 ms 1740 KB Output is correct
38 Correct 138 ms 1828 KB Output is correct
39 Correct 101 ms 1832 KB Output is correct
40 Correct 120 ms 1740 KB Output is correct
41 Correct 133 ms 1784 KB Output is correct
42 Correct 116 ms 1888 KB Output is correct
43 Correct 112 ms 1688 KB Output is correct
44 Correct 119 ms 1608 KB Output is correct

Subtask #3
64.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 1856 KB Partially correct
2 Partially correct 124 ms 1732 KB Partially correct
3 Partially correct 89 ms 1888 KB Partially correct
4 Partially correct 119 ms 1736 KB Partially correct
5 Partially correct 129 ms 1776 KB Partially correct
6 Correct 78 ms 1516 KB Output is correct
7 Correct 48 ms 1344 KB Output is correct
8 Partially correct 126 ms 1880 KB Partially correct
9 Partially correct 115 ms 1624 KB Partially correct
10 Partially correct 117 ms 1636 KB Partially correct
11 Partially correct 105 ms 1628 KB Partially correct
12 Partially correct 141 ms 1776 KB Partially correct
13 Partially correct 73 ms 1724 KB Partially correct
14 Correct 89 ms 1484 KB Output is correct
15 Correct 84 ms 1328 KB Output is correct
16 Correct 79 ms 1220 KB Output is correct
17 Partially correct 100 ms 1608 KB Partially correct
18 Correct 73 ms 1236 KB Output is correct