이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |