제출 #530766

#제출 시각아이디문제언어결과실행 시간메모리
530766c28dnv9q3Monster Game (JOI21_monster)C++17
10 / 100
260 ms3536 KiB
#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;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...