oj.uz

Submission #545734

# Submission time Handle Problem Language Result Execution time Memory
545734 2022-04-05T10:09:07 Z alextodoran Monster Game (JOI21_monster) C++17
0 / 100
 67 ms 4228 KB 
#include <bits/stdc++.h>

using namespace std;

bool Query (int a, int b);

vector <vector <int>> cmp;
bool ask (int a, int b) {
    if (a > b) {
        swap(a, b);
        if (cmp[a][b] == -1) {
            cmp[a][b] = Query(a, b);
        }
        return !cmp[a][b];
    } else {
        if (cmp[a][b] == -1) {
            cmp[a][b] = Query(a, b);
        }
        return cmp[a][b];
    }
}

void mergeSort (vector <int> :: iterator l, vector <int> :: iterator r) {
    int len = r - l;
    if (len != 1) {
        int mid = len / 2;
        mergeSort(l, l + mid);
        mergeSort(l + mid, r);
        vector <int> aux (len);
        merge(l, l + mid, l + mid, r, aux.begin(), [&] (const int &i, const int &j) {
            return ask(j, i);
        });
        copy(aux.begin(), aux.end(), l);
    }
}

vector <int> Solve (int N) {
    cmp = vector <vector <int>> (N, vector <int> (N, -1));
    vector <int> order (N);
    iota(order.begin(), order.end(), 0);
    mergeSort(order.begin(), order.end());
    int K = min(N, 7);
    vector <int> cnt (K, 0);
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            if (i != j) {
                cnt[i] += ask(order[i], order[j]);
            }
        }
    }
    vector <int> aux (N);
    iota(aux.begin(), aux.end(), 0);
    sort(aux.begin(), aux.end(), [&] (const int &i, const int &j) {
        return cnt[i] < cnt[j];
    });
    int currMin = (ask(order[aux[0]], order[aux[1]]) == true ? aux[0] : aux[1]);
    reverse(order.begin(), order.begin() + currMin + 1);
    while (currMin + 1 < N) {
        int nextMin = currMin + 1;
        while (ask(order[currMin], order[nextMin]) == false) {
            nextMin++;
        }
        reverse(order.begin() + currMin + 1, order.begin() + nextMin + 1);
        currMin = nextMin;
    }
    vector <int> ret (N);
    for (int i = 0; i < N; i++) {
        ret[order[i]] = i;
    }
    return ret;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 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 0 ms 208 KB Output is correct
7 Correct 1 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 Incorrect 14 ms 336 KB Wrong Answer [4]
17 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 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 0 ms 208 KB Output is correct
7 Correct 1 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 Incorrect 14 ms 336 KB Wrong Answer [4]
17 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 4228 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -