#include "monster.h"
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void print(string pre, vector<int> a) {
cout << pre << " ";
for (int i = 0; i < a.size(); ++i) {
cout << a[i] << " ";
}
cout << "\n";
}
bool compare(int a, int b, int N) {
if (a >= N) return true;
if (b >= N) return false;
return Query(a, b);
}
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> T) {
vector<int> min = vector<int>{0, 1};
vector<int> nMin;
bool cont;
for (int i = 0; true; ++i) {
cont = false;
for (int j = 0; j < min.size(); ++j) if (i % N == min[j]) cont = true;
if (cont) continue;
min.push_back(i % N);
if (min.size() == 4) {
int count[] = {0, 0, 0, 0};
for (int j = 0; j < 4; ++j) {
for (int k = j + 1; k < 4; ++k) {
if (Query(T[min[j]], T[min[k]])) {
count[k]++;
} else {
count[j]++;
}
}
}
nMin = vector<int>();
for (int j = 0; j < 4; ++j) {
if (count[j] >= 2) nMin.push_back(min[j]);
}
min = nMin;
if (i >= 2 * N) break;
}
}
if (min.size() == 3) {
int count[] = {0, 0, 0};
for (int i = 0; i < min.size(); ++i) {
for (int j = 0; j < N; ++j) {
if (min[i] == j) continue;
if (Query(T[min[i]], T[j])) count[i]++;
}
}
nMin = vector<int>();
for (int i = 0; i < min.size(); ++i) {
if (count[i] == 1) nMin.push_back(min[i]);
}
min = nMin;
}
print("possible", min);
return Query(T[min[0]], T[min[1]]) ? min[0] : min[1];
}
std::vector<int> Solve(int N) {
cout << "start\n";
vector<int> T = sort(5, 0, N);
print("t", T);
int x = findMin(N, T);
cout << "min " << x << "\n";
rev(T, 0, x);
print("t", T);
for (int s = x; s < N - 1;) {
print("t", T);
for (int i = s + 1; i < N; ++i) {
cout << s << " " << i << "\n";
if (Query(T[s], T[i])) {
rev(T, s + 1, i);
s = i;
break;
}
}
}
vector<int> erg = vector<int>(N, 0);
for (int i = 0; i < N; ++i) {
erg[T[i]] = i;
}
print("t", T);
print("erg", erg);
return erg;
}
Compilation message
monster.cpp: In function 'void print(std::string, std::vector<int>)':
monster.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = 0; i < a.size(); ++i) {
| ~~^~~~~~~~~~
monster.cpp: In function 'std::vector<int> sort(int, int, int)':
monster.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i = 0; i < c.size(); ++i) {
| ~~^~~~~~~~~~
monster.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if (iA < a.size() && iB < b.size()) {
| ~~~^~~~~~~~~~
monster.cpp:29:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if (iA < a.size() && iB < b.size()) {
| ~~~^~~~~~~~~~
monster.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if (iA == a.size()) {
| ~~~^~~~~~~~~~~
monster.cpp: In function 'int findMin(int, std::vector<int>)':
monster.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int j = 0; j < min.size(); ++j) if (i % N == min[j]) cont = true;
| ~~^~~~~~~~~~~~
monster.cpp:86:27: 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 < min.size(); ++i) {
| ~~^~~~~~~~~~~~
monster.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < min.size(); ++i) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
200 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
200 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
200 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
