#include<bits/stdc++.h>
#include "monster.h"
using namespace std;
#define al(a) a.begin(), a.end()
random_device rd;
mt19937 rnd(1);
typedef int ll;
map<pair<ll, ll>, bool> m;
ll N;
bool query(ll a, ll b) {
return (m.find(make_pair(a, b)) != m.end() ? m[make_pair(a, b)] : (m[make_pair(a, b)] = !(m[make_pair(b, a)] = Query(b, a))));
}
void grnd() {
ll x = rnd() % n;
ll y;
do {
y = rnd() % n;
} while (x == y);
query(x, y);
}
void s(vector<ll>& all) {
if (all.size() <= 1) {
return;
}
if (all.size() <= 30) {
vector<pair<ll, ll>> now;
map<ll, vector<ll>> big, sma;
for (ll i = 0; i < all.size(); i++) {
ll cb = 0;
for (ll j = 0; j < all.size(); j++) {
if (i != j) {
if (query(all[i], all[j])) {
sma[all[i]].push_back(all[j]);
} else {
cb++;
big[all[i]].push_back(all[j]);
}
}
}
now.emplace_back(cb, all[i]);
}
sort(now.rbegin(), now.rend());
if (sma[now[0].second].empty()) {
if (now.size() > 2 && find(al(sma[now[2].second]), now[1].second) != sma[now[2].second].end()) {
swap(now[1], now[2]);
}
} else {
if (find(al(sma[now[1].second]), now[0].second) != sma[now[1].second].end()) {
swap(now[0], now[1]);
}
}
if (big[now[now.size() - 1].second].empty()) {
if (now.size() > 2 && find(al(big[now[now.size() - 3].second]), now[now.size() - 2].second) != big[now[now.size() - 3].second].end()) {
swap(now[now.size() - 2], now[now.size() - 3]);
}
} else {
if (find(al(big[now[now.size() - 2].second]), now.back().second) != big[now[now.size() - 2].second].end()) {
swap(now[now.size() - 2], now.back());
}
}
for (ll i = 0; i < all.size(); i++) {
all[i] = now[i].second;
}
return;
}
ll x, now;
vector<ll> sm, bi;
for (ll i = 0; i < 5; i++) {
grnd();
}
do {
x = rnd() % all.size();
now = all[x];
sm.clear();
bi.clear();
grnd();
for (ll j = 0; j < all.size(); j++) {
if (j != x) {
if (query(now, all[j])) {
sm.push_back(all[j]);
} else {
bi.push_back(all[j]);
}
}
}
} while (sm.size() < 6 || bi.size() < 6);
s(sm);
s(bi);
if (!sm.empty() && !bi.empty()) {
swap(sm.back(), bi[0]);
}
all.clear();
for (auto i : sm) {
all.push_back(i);
}
all.push_back(now);
for (auto i : bi) {
all.push_back(i);
}
}
vector<ll> Solve(ll n) {
N = n;
vector<ll> all;
for (ll i = 0; i < n; i++) {
all.push_back(i);
}
s(all);
vector<ll> ans(n);
for (ll i = 0; i < n; i++) {
ans[all[i]] = i;
}
return ans;
}
Compilation message
monster.cpp: In function 'void grnd()':
monster.cpp:22:24: error: 'n' was not declared in this scope
22 | ll x = rnd() % n;
| ^
monster.cpp: In function 'void s(std::vector<int>&)':
monster.cpp:37:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (ll i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
monster.cpp:39:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (ll j = 0; j < all.size(); j++) {
| ~~^~~~~~~~~~~~
monster.cpp:70:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (ll i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
monster.cpp:86:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (ll j = 0; j < all.size(); j++) {
| ~~^~~~~~~~~~~~
