#include<bits/stdc++.h>
#include "monster.h"
using namespace std;
random_device rd;
mt19937 rnd(rd());
typedef int ll;
void s(vector<ll>& all) {
if (all.empty()) {
return;
}
if (true) {
vector<pair<ll, ll>> now;
vector<vector<ll>> big(all.size()), sma(all.size());
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[i].push_back(j);
} else {
cb++;
big[i].push_back(j);
}
}
}
now.emplace_back(cb, i);
}
sort(now.rbegin(), now.rend());
if (sma[now[1].second][0] == now[0].second) {
swap(now[0], now[1]);
}
if (big[now[now.size() - 2].second][0] == now.back().second) {
swap(now[now.size() - 2], now.back());
}
for (ll i = 0; i < all.size(); i++) {
all[i] = now[i].second;
}
return;
}
ll x = rnd() % all.size();
ll now = all[x];
cout << now << '\n';
vector<ll> sm, bi;
for (ll j = 0; j < all.size(); j++) {
if (j != x) {
if (Query(now, all[j])) {
cout << "< " << all[j] << '\n';
sm.push_back(all[j]);
} else {
cout << "> " << all[j] << '\n';
bi.push_back(all[j]);
}
}
}
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;
}
for (auto i : ans) {
cout << i << ' ';
}
cout << '\n';
return ans;
}
Compilation message
monster.cpp: In function 'void s(std::vector<int>&)':
monster.cpp:18:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (ll i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
monster.cpp:20:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (ll j = 0; j < all.size(); j++) {
| ~~^~~~~~~~~~~~
monster.cpp:39:34: 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 i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
monster.cpp:48:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (ll j = 0; j < all.size(); j++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [0] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [0] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
1320 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
