#include<bits/stdc++.h>
#include "monster.h"
using namespace std;
#define al(a) a.begin(), a.end()
random_device rd;
mt19937 rnd(0);
typedef int ll;
map<pair<ll, ll>, bool> m;
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 s(vector<ll>& all) {
if (all.size() <= 1) {
return;
}
if (all.size() <= 11) {
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 (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.back().second].empty()) {
if (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;
do {
x = rnd() % all.size();
now = all[x];
sm.clear();
bi.clear();
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() == 1 || bi.size() == 1);
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) {
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 s(std::vector<int>&)':
monster.cpp:26:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (ll i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
monster.cpp:28:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (ll j = 0; j < all.size(); j++) {
| ~~^~~~~~~~~~~~
monster.cpp:59:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (ll i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
monster.cpp:71:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (ll j = 0; j < all.size(); j++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
448 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
0 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Incorrect |
7 ms |
1112 KB |
Wrong Answer [3] |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
448 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
0 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Incorrect |
7 ms |
1112 KB |
Wrong Answer [3] |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
2620 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
