#include "monster.h"
#include <iostream>
namespace {
} // namespace
std::vector<int> quick(std::vector<int> a) {
std::vector<int> left = std::vector<int>(), right = std::vector<int>();
if (a.size() < 2) {
return a;
}else if(a.size() == 2){
std::vector<int> b = std::vector<int>();
if (Query(a[0], a[1])) {
b.push_back(a[0]);
b.push_back(a[1]);
}
else {
b.push_back(a[1]);
b.push_back(a[0]);
}
return b;
}
int pivot = a[a.size() / 2];
for (int i = 0; i < a.size(); i++) {
if (!(i == (a.size() / 2))) {
if (Query(pivot, a[i])) {
left.push_back(a[i]);
}
else {
right.push_back(a[i]);
}
}
}
if (left.size() == 0) {
int min = 0;
for (int i = 1; i < right.size(); i++) {
if (Query(right[min], right[i])) {
min = i;
}
}
left.push_back(right[min]);
right.erase(right.begin() + min);
}
else if (right.size() == 0) {
int max = 0;
for (int i = 1; i < left.size(); i++) {
if (Query(left[i], left[max])) {
max = i;
}
}
right.push_back(left[max]);
left.erase(left.begin() + max);
}
else {
int min = 0;
for (int i = 1; i < right.size(); i++) {
if (Query(right[min], right[i])) {
min = i;
}
}
int max = 0;
for (int i = 1; i < left.size(); i++) {
if (Query(left[i], left[max])) {
max = i;
}
}
right.push_back(left[max]);
left.push_back(right[min]);
left.erase(left.begin() + max);
right.erase(right.begin() + min);
if (right.size() == 1) {
for (int i = 0; i < left.size(); i++) {
if (Query(left[i], right[0])) {
left.push_back(right[0]);
right.erase(right.begin());
goto END;
}
}
}
else if (left.size() == 1) {
for (int i = 0; i < right.size(); i++) {
if (!Query(right[i], left[0])) {
right.push_back(left[0]);
left.erase(left.begin());
goto END;
}
}
}
}
END: std::vector<int> end = std::vector<int>();
std::vector<int> l;
if (left.size() == 3) {
for (int i = 0; i < 3; i++) {
if (Query(left[i], pivot)) {
l = left;
left = std::vector<int>();
for (int j = 0; j < 3; j++) {
if (j != i) {
left.push_back(l[j]);
}
}
int x = l[i];
l = quick(left);
l.push_back(x);
goto SKIP;
}
}
}
else {
l = quick(left);
}
SKIP: end = l;
end.push_back(pivot);
std::vector<int> r = std::vector<int>();
if (right.size() == 3) {
for (int i = 0; i < 3; i++) {
if (Query(pivot, right[i])) {
r = right;
right = std::vector<int>();
for (int j = 0; j < 3; j++) {
if (j != i) {
right.push_back(r[j]);
}
}
int x = r[i];
right = quick(right);
r.push_back(x);
r.push_back(right[0]);
r.push_back(right[1]);
goto SKIP2;
}
}
}
else {
r = quick(right);
}
SKIP2: for (int i = 0; i < r.size(); i++) {
end.push_back(r[i]);
}
return end;
}
std::vector<int> Solve(int N) {
std::vector<int> T(N);
for (int i = 0; i < N; i++) {
T[i] = i;
}
T = quick(T);
std::vector<int> T2 = std::vector<int>(N);
for (int i = 0; i < N; i++) {
T2[T[i]] = i;
}
for (int i = 0; i < N; i++) {
std::cout << T2[i] << " ";
}
return T2;
}
Compilation message
monster.cpp: In function 'std::vector<int> quick(std::vector<int>)':
monster.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
monster.cpp:26:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if (!(i == (a.size() / 2))) {
| ~~^~~~~~~~~~~~~~~~~
monster.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 1; i < right.size(); i++) {
| ~~^~~~~~~~~~~~~~
monster.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 1; i < left.size(); i++) {
| ~~^~~~~~~~~~~~~
monster.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 1; i < right.size(); i++) {
| ~~^~~~~~~~~~~~~~
monster.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 1; i < left.size(); i++) {
| ~~^~~~~~~~~~~~~
monster.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < left.size(); i++) {
| ~~^~~~~~~~~~~~~
monster.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < right.size(); i++) {
| ~~^~~~~~~~~~~~~~
monster.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | SKIP2: for (int i = 0; i < r.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
428 KB |
Wrong Answer [0] |
| 2 |
Halted |
0 ms |
0 KB |
- |
