oj.uz

답안 #528862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528862 2022-02-21T15:46:36 Z c28dnv9q3 Monster Game (JOI21_monster) C++17
71 / 100
 175 ms 404 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 >= 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 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 1 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 292 KB Output is correct
13 Correct 1 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 27 ms 296 KB Output is correct
17 Correct 13 ms 292 KB Output is correct
18 Correct 12 ms 296 KB Output is correct
19 Correct 16 ms 200 KB Output is correct
20 Correct 27 ms 284 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 292 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 200 KB Output is correct
26 Correct 18 ms 296 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 288 KB Output is correct
30 Correct 2 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 19 ms 292 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 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 1 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 292 KB Output is correct
13 Correct 1 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 27 ms 296 KB Output is correct
17 Correct 13 ms 292 KB Output is correct
18 Correct 12 ms 296 KB Output is correct
19 Correct 16 ms 200 KB Output is correct
20 Correct 27 ms 284 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 292 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 200 KB Output is correct
26 Correct 18 ms 296 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 288 KB Output is correct
30 Correct 2 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 19 ms 292 KB Output is correct
33 Correct 161 ms 284 KB Output is correct
34 Correct 130 ms 280 KB Output is correct
35 Correct 150 ms 284 KB Output is correct
36 Correct 132 ms 284 KB Output is correct
37 Correct 95 ms 280 KB Output is correct
38 Correct 168 ms 288 KB Output is correct
39 Correct 65 ms 396 KB Output is correct
40 Correct 72 ms 276 KB Output is correct
41 Correct 172 ms 280 KB Output is correct
42 Correct 158 ms 404 KB Output is correct
43 Correct 42 ms 292 KB Output is correct
44 Correct 104 ms 280 KB Output is correct

Subtask #3
46.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 158 ms 284 KB Partially correct
2 Partially correct 115 ms 292 KB Partially correct
3 Partially correct 91 ms 284 KB Partially correct
4 Partially correct 133 ms 280 KB Partially correct
5 Partially correct 116 ms 288 KB Partially correct
6 Partially correct 119 ms 284 KB Partially correct
7 Partially correct 77 ms 280 KB Partially correct
8 Partially correct 116 ms 284 KB Partially correct
9 Partially correct 133 ms 280 KB Partially correct
10 Partially correct 107 ms 288 KB Partially correct
11 Partially correct 107 ms 280 KB Partially correct
12 Partially correct 108 ms 280 KB Partially correct
13 Partially correct 96 ms 284 KB Partially correct
14 Partially correct 98 ms 288 KB Partially correct
15 Correct 91 ms 292 KB Output is correct
16 Correct 71 ms 292 KB Output is correct
17 Partially correct 175 ms 280 KB Partially correct
18 Correct 75 ms 292 KB Output is correct