제출 #530766

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

monster

#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";
}

int higher[1024];
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);

    int ii;
    for (int i = 0; i < low.size(); ++i) {
        ii = i + 1;
        while (ii < low.size() && higher[i] <= 3) {
            compare(low[i], low[ii], N);
            ii++;
        }
    }

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

    print("possible: ", possible);

    for (int i = 0; i < possible.size(); ++i) {
        for (int j = i + 1; j < possible.size(); ++j) {
            compare(possible[i], possible[j], N);
        }
    }

    vector<int> min;
    for (int i = 0; i < possible.size(); ++i) {
        if (higher[possible[i]] == 1) min.push_back(possible[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(10, 0, N);

    int ind;
    int x = findMin(N);
    for (int i = 0; i < N; ++i) {
        if (T[i] == x) ind = i;
    }
    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 {0};
        }
    }

    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: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:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (iA < a.size() && iB < b.size()) {
      |             ~~~^~~~~~~~~~
monster.cpp:44:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (iA < a.size() && iB < b.size()) {
      |                              ~~~^~~~~~~~~~
monster.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (iA == a.size()) {
      |                 ~~~^~~~~~~~~~~
monster.cpp: In function 'int findMin(int)':
monster.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < low.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
monster.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while (ii < low.size() && higher[i] <= 3) {
      |                ~~~^~~~~~~~~~~~
monster.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < low.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
monster.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < possible.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
monster.cpp:93:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int j = i + 1; j < possible.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~
monster.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 0; i < possible.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:113:9: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     int ind;
      |         ^~~

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