제출 #530946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530946		c28dnv9q3	Monster Game (JOI21_monster)	C++17	100 / 100	138 ms	4236 KiB

monster

#include "monster.h"
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int len = 12;

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

int higher[1 << len];
map<pair<int, int>, int> quer;

bool cmp(int a, int b, int N) {
    if (a >= N) return true;
    if (b >= N) return false;
    //cout << a << " " << b << "\n";
    bool q = Query(a, b);
    if (q) higher[a]++; else higher[b]++;
    return q;
}

bool compare(int a, int b, int N) {
    if (quer[{a, b}] != 0) return quer[{a, b}] == 2;
    bool q = cmp(a, b, N);
    quer[{a, b}] = q ? 2 : 1;
    quer[{b, a}] = q ? 1 : 2;
    return q;
}

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> low;

    for (int i = 0; i < N; ++i) {
        if (higher[i] <= 3) low.push_back(i);
    }

    print("possible: ", low);

    for (int i = 0; i < low.size(); ++i) {
        for (int j = 0; j < low.size(); ++j) {
            if (i == j) continue;
            if (higher[low[i]] > 3 || higher[low[j]] > 3) continue;
            compare(low[i], low[j], N);
        }
    }

    print("possible: ", low);

    vector<int> min;
    for (int i = 0; i < low.size(); ++i) {
        if (higher[low[i]] == 1) min.push_back(low[i]);
    }

    print("last: ", min);

    //for (int i = 0; i < N; ++i) cout << higher[i]; cout << "\n";

    return compare(min[0], min[1], N) ? min[0] : min[1];
}

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

    int ind = -1;
    int x = findMin(N);
    for (int i = 0; i < N; ++i) {
        if (T[i] == x) ind = i;
    }
    if (ind == -1) return {};
    rev(T, 0, ind);

    for (int s = ind; s < N - 1;) {
        for (int i = s + 1; i < N; ++i) {
            if (compare(T[s], T[i], N)) {
                rev(T, s + 1, i);
                s = i;
                break;
            }
            if (i == N - 1) return {};
        }
    }

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

    return erg;
}

컴파일 시 표준 에러 (stderr) 메시지

monster.cpp: In function 'void print(std::string, std::vector<int>)':
monster.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp: In function 'std::vector<int> sort(int, int, int)':
monster.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (iA < a.size() && iB < b.size()) {
      |             ~~~^~~~~~~~~~
monster.cpp:46:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (iA < a.size() && iB < b.size()) {
      |                              ~~~^~~~~~~~~~
monster.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (iA == a.size()) {
      |                 ~~~^~~~~~~~~~~
monster.cpp: In function 'int findMin(int)':
monster.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < low.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
monster.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int j = 0; j < low.size(); ++j) {
      |                         ~~^~~~~~~~~~~~
monster.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < low.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75