oj.uz

Submission #679824

# Submission time Handle Problem Language Result Execution time Memory
679824 2023-01-09T11:27:32 Z bashkort Monster Game (JOI21_monster) C++17
0 / 100
 95 ms 300 KB 
#include "monster.h"
#include <bits/stdc++.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);

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

    int k = min(n, 10);

    vector<int> win(k);

    for (int i = 0; i < k; ++i) {
        for (int j = i + 1; j < k; ++j) {
            if (Query(ord[i], ord[j])) {
                win[i] += 1;
            } else {
                win[j] += 1;
            }
        }
    }

    int fi = min_element(win.begin(), win.end()) - win.begin();
    int se = min_element(win.begin() + fi + 1, win.end()) - win.begin();

    int x = Query(fi, se) ? fi : se;

    rotate(ord.begin(), ord.begin() + x, ord.begin() + x + 1);

    x = 0;

    for (int i = 1, j = 1; i < n; i = j) {
        while (Query(ord[j], ord[x])) {
            j += 1;
        }

        j += 1;
        reverse(ord.begin() + i, ord.begin() + j);

        x = j - 1;
    }

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

    return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 89 ms 296 KB Partially correct
2 Partially correct 95 ms 288 KB Partially correct
3 Incorrect 60 ms 300 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -