#include "monster.h"
#include <iostream>
#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 {
int cnt[maxn];
bool res[maxn][maxn];
bool found[maxn][maxn];
} // namespace
bool que(int a, int b) {
if (found[a][b]) return res[a][b];
bool ret = Query(a, b);
res[a][b] = ret, res[b][a] = ret ^ 1;
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);
//pary(cand.begin(), cand.end());
vector<pii> cur;
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) {
debug(49, j);
cur.erase(cur.begin() + j);
}
}
if (loss < 2) {
cur.push_back({i, loss});
}
}
//cout << 7122 << endl;
//for (auto i:cur) cout << i.ff << " ";
//cout << endl;
int big;
if (cur.size() == 2) {
if (que(cand[cur[0].ff], cand[cur[1].ff])) 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;
}
}
}
//debug(big);
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:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0;i < v.size();i++) {
| ~~^~~~~~~~~~
monster.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if (i < (v.size() / 2)) lef.push_back(v[i]);
| ~~^~~~~~~~~~~~~~~~
monster.cpp:43:19: 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 < lef.size();i++) {
| ~~^~~~~~~~~~~~
monster.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while (ind < rig.size() && que(lef[i], rig[ind])) {
| ~~~~^~~~~~~~~~~~
monster.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while (ind < rig.size()) ret.push_back(rig[ind++]);
| ~~~~^~~~~~~~~~~~
monster.cpp: At global scope:
monster.cpp:21:6: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
21 | int cnt[maxn];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 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 |
1 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 |
108 ms |
1292 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
