#include "monster.h"
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <time.h>
#include <random>
#define maxn 1005
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ";debug(b ...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
namespace {
bool res[maxn][maxn];
bool found[maxn][maxn];
int num = 0, save = 0;
} // namespace
bool que(int a, int b) {
if (found[a][b]) return save++, res[a][b];
bool ret = Query(a, b);
found[a][b] = found[b][a] = 1;
res[a][b] = ret, res[b][a] = ret ^ 1;
num++;
return ret;
}
void mergesort(vector<int> &v) {
if (v.size() <= 1) {
return;
}
vector<int> lef, rig;
for (int i = 0;i < v.size();i++) {
if (i < (v.size() / 2)) lef.push_back(v[i]);
else rig.push_back(v[i]);
}
mergesort(lef), mergesort(rig);
vector<int> ret;
int ind = 0;
for (int i = 0;i < lef.size();i++) {
while (ind < rig.size() && que(lef[i], rig[ind])) {
ret.push_back(rig[ind]);
ind++;
}
ret.push_back(lef[i]);
}
while (ind < rig.size()) ret.push_back(rig[ind++]);
v = ret;
}
vector<int> Solve(int N) {
vector<int> ret;
vector<int> cand;
for (int i = 0;i < N;i++) cand.push_back(i);
mergesort(cand);
//cout << num << endl;
vector<pii> cur;
bool done = 0;
for (int i = N - 1;i >= 0;i--) {
int loss = 0;
for (auto &j:cur) {
if (que(cand[i], cand[j.ff])) j.ss++;
else loss++;
}
for (int j = cur.size() - 1;j >= 0;j--) {
if (cur[j].ss > 1) {
cur.erase(cur.begin() + j);
} else if (cur[j].ff > i + 3) {
done = 1;
break;
}
}
if (done) break;
if (loss < 2) cur.push_back({i, loss});
}
//cout << num << " " << save << endl;
assert(cur.size());
int big;
if (cur.size() == 1) big = cur[0].ff;
else if (cur.size() == 2) {
if (cur[0].ff == cur[1].ff + 1) big = cur[1].ff;
else big = cur[0].ff;
} else {
big = cur[0].ff;
for (int i = 0;i < 2;i++) {
if (cur[i + 1].ff == cur[i].ff - 1) big = cur[i + 1].ff;
else {
break;
}
}
}
for (int i = big;i < N;i++) ret.push_back(cand[i]);
int comp = N - 1;
for (int i = big - 1;i >= 0;i--) {
if (que(cand[i], cand[comp])) {
for (int j = i;j < big;j++) ret.push_back(cand[j]);
comp = big - 1, big = i;
}
}
reverse(ret.begin(), ret.end());
vector<int> a (N, 0);
for (int i = 0;i < N;i++) a[ret[i]] = i;
return a;
}
/*
5
3 1 4 2 0
8
7 3 4 2 1 5 6 0
10
0 2 8 3 9 4 6 7 5 1
*/
Compilation message
monster.cpp: In function 'void mergesort(std::vector<int>&)':
monster.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0;i < v.size();i++) {
| ~~^~~~~~~~~~
monster.cpp:40:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (i < (v.size() / 2)) lef.push_back(v[i]);
| ~~^~~~~~~~~~~~~~~~
monster.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0;i < lef.size();i++) {
| ~~^~~~~~~~~~~~
monster.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | while (ind < rig.size() && que(lef[i], rig[ind])) {
| ~~~~^~~~~~~~~~~~
monster.cpp:53:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (ind < rig.size()) ret.push_back(rig[ind++]);
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Correct |
1 ms |
200 KB |
Output is correct |
| 5 |
Correct |
1 ms |
200 KB |
Output is correct |
| 6 |
Correct |
1 ms |
200 KB |
Output is correct |
| 7 |
Correct |
1 ms |
200 KB |
Output is correct |
| 8 |
Correct |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
1 ms |
200 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [3] |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Correct |
1 ms |
200 KB |
Output is correct |
| 5 |
Correct |
1 ms |
200 KB |
Output is correct |
| 6 |
Correct |
1 ms |
200 KB |
Output is correct |
| 7 |
Correct |
1 ms |
200 KB |
Output is correct |
| 8 |
Correct |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
1 ms |
200 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [3] |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
2240 KB |
Output is correct |
| 2 |
Correct |
111 ms |
2440 KB |
Output is correct |
| 3 |
Correct |
107 ms |
2148 KB |
Output is correct |
| 4 |
Correct |
78 ms |
2240 KB |
Output is correct |
| 5 |
Correct |
88 ms |
2256 KB |
Output is correct |
| 6 |
Correct |
84 ms |
2280 KB |
Output is correct |
| 7 |
Correct |
73 ms |
2316 KB |
Output is correct |
| 8 |
Correct |
125 ms |
2212 KB |
Output is correct |
| 9 |
Runtime error |
125 ms |
4348 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
