oj.uz

Submission #528858

# Submission time Handle Problem Language Result Execution time Memory
528858 2022-02-21T15:33:49 Z c28dnv9q3 Monster Game (JOI21_monster) C++17
56 / 100
 187 ms 408 KB 
#include "monster.h"
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void print(string pre, vector<int> a) {
    return;
    cout << pre << " ";
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << " ";
    }
    cout << "\n";
}

bool compare(int a, int b, int N) {
    if (a >= N) return true;
    if (b >= N) return false;
    return Query(a, b);
}

vector<int> sort(int l, int o, int N) {
    if (l == 0) return std::vector<int>{o};
    vector<int> a = sort(l - 1, o, N);
    vector<int> b = sort(l - 1, o + (1 << (l - 1)), N);
    vector<int> c(a.size() + b.size());
    int iA = 0;
    int iB = 0;
    for (int i = 0; i < c.size(); ++i) {
        if (iA < a.size() && iB < b.size()) {
            if (compare(a[iA], b[iB], N)) {
                c[i] = b[iB++];
            } else {
                c[i] = a[iA++];
            }
        } else {
            if (iA == a.size()) {
                c[i] = b[iB++];
            } else {
                c[i] = a[iA++];
            }
        }
    }
    return c;
}

void rev(vector<int> &T, int a, int b) {
    for (int i = 0; i < (1 + b - a) / 2; ++i) {
        swap(T[a + i], T[b - i]);
    }
}

int findMin(int N, vector<int> T) {
    vector<int> min = vector<int>{0, 1};
    vector<int> nMin;
    bool cont;
    for (int i = 0; true; ++i) {
        cont = false;
        for (int j = 0; j < min.size(); ++j) if (i % N == min[j]) cont = true;
        if (cont) continue;
        min.push_back(i % N);

        if (min.size() == 4) {
            int count[] = {0, 0, 0, 0};
            for (int j = 0; j < 4; ++j) {
                for (int k = j + 1; k < 4; ++k) {
                    if (Query(T[min[j]], T[min[k]])) {
                        count[k]++;
                    } else {
                        count[j]++;
                    }
                }
            }

            nMin = vector<int>();
            for (int j = 0; j < 4; ++j) {
                if (count[j] >= 2) nMin.push_back(min[j]);
            }
            min = nMin;

            if (i >= 2 * N) break;
        }
    }

    if (min.size() == 3) {
        int count[] = {0, 0, 0};
        for (int i = 0; i < min.size(); ++i) {
            for (int j = 0; j < N; ++j) {
                if (min[i] == j) continue;
                if (Query(T[min[i]], T[j])) count[i]++;
            }
        }
        nMin = vector<int>();
        for (int i = 0; i < min.size(); ++i) {
            if (count[i] == 1) nMin.push_back(min[i]);
        }
        min = nMin;
    }

    print("possible", min);

    return Query(T[min[0]], T[min[1]]) ? min[0] : min[1];
}

std::vector<int> Solve(int N) {
    vector<int> T = sort(10, 0, N);

    print("t", T);

    int x = findMin(N, T);
    rev(T, 0, x);

    print("t", T);

    for (int s = x; s < N - 1;) {
        print("t", T);
        for (int i = s + 1; i < N; ++i) {
            if (Query(T[s], T[i])) {
                rev(T, s + 1, i);
                s = i;
                break;
            }
        }
    }

    vector<int> erg = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        erg[T[i]] = i;
    }

    print("t", T);

    print("erg", erg);

    return erg;
}

Compilation message

monster.cpp: In function 'void print(std::string, std::vector<int>)':
monster.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp: In function 'std::vector<int> sort(int, int, int)':
monster.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (iA < a.size() && iB < b.size()) {
      |             ~~~^~~~~~~~~~
monster.cpp:30:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (iA < a.size() && iB < b.size()) {
      |                              ~~~^~~~~~~~~~
monster.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if (iA == a.size()) {
      |                 ~~~^~~~~~~~~~~
monster.cpp: In function 'int findMin(int, std::vector<int>)':
monster.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j = 0; j < min.size(); ++j) if (i % N == min[j]) cont = true;
      |                         ~~^~~~~~~~~~~~
monster.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < min.size(); ++i) {
      |                         ~~^~~~~~~~~~~~
monster.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int i = 0; i < min.size(); ++i) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 2 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 2 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 2 ms 200 KB Output is correct
14 Correct 2 ms 200 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 22 ms 292 KB Output is correct
17 Correct 33 ms 324 KB Output is correct
18 Correct 22 ms 280 KB Output is correct
19 Correct 23 ms 292 KB Output is correct
20 Correct 23 ms 288 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 25 ms 280 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 21 ms 296 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 2 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 2 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 2 ms 200 KB Output is correct
14 Correct 2 ms 200 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 22 ms 292 KB Output is correct
17 Correct 33 ms 324 KB Output is correct
18 Correct 22 ms 280 KB Output is correct
19 Correct 23 ms 292 KB Output is correct
20 Correct 23 ms 288 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 25 ms 280 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 21 ms 296 KB Output is correct
33 Correct 117 ms 288 KB Output is correct
34 Correct 112 ms 408 KB Output is correct
35 Correct 152 ms 280 KB Output is correct
36 Correct 113 ms 280 KB Output is correct
37 Correct 144 ms 288 KB Output is correct
38 Correct 172 ms 284 KB Output is correct
39 Correct 99 ms 404 KB Output is correct
40 Correct 167 ms 284 KB Output is correct
41 Correct 165 ms 404 KB Output is correct
42 Correct 180 ms 284 KB Output is correct
43 Correct 93 ms 292 KB Output is correct
44 Correct 96 ms 404 KB Output is correct

Subtask #3
31.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 126 ms 280 KB Partially correct
2 Partially correct 181 ms 408 KB Partially correct
3 Partially correct 133 ms 280 KB Partially correct
4 Partially correct 138 ms 320 KB Partially correct
5 Partially correct 68 ms 280 KB Partially correct
6 Partially correct 85 ms 280 KB Partially correct
7 Partially correct 135 ms 200 KB Partially correct
8 Partially correct 182 ms 280 KB Partially correct
9 Partially correct 187 ms 280 KB Partially correct
10 Partially correct 165 ms 288 KB Partially correct
11 Partially correct 140 ms 404 KB Partially correct
12 Partially correct 174 ms 272 KB Partially correct
13 Partially correct 127 ms 292 KB Partially correct
14 Partially correct 86 ms 280 KB Partially correct
15 Partially correct 87 ms 288 KB Partially correct
16 Partially correct 96 ms 292 KB Partially correct
17 Partially correct 140 ms 284 KB Partially correct
18 Partially correct 88 ms 200 KB Partially correct