/*
author: Maksim1744
created: 12.02.2021 00:39:20
*/
#include "bits/stdc++.h"
#include "grader.h"
using namespace std;
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T>& v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T>& v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "C:/C++ libs/print.cpp"
#else
#define show(...) 42
#define mclock 42
#define shows 42
#define debug if (false)
#endif
mt19937_64 rng(198237);
ll rnd (ll l, ll r) { return (ll)(rng() % (r - l + 1)) + l; }
ll rnd (ll r) { return rng() % r; }
ll rnd () { return rng(); }
ld rndf() { return (ld)rng() / (ld)ULLONG_MAX; }
ld rndf(ld l, ld r) { return rndf() * (r - l) + l; }
void solve(int n) {
vector<int> nums;
for (int i = 0; i < n; ++i) {
nums.pb(i + 1);
}
for (int i = 0; i < nums.size(); ++i)
swap(nums[i], nums[rnd(i, nums.size() - 1)]);
vector<int> p(n, -1);
map<vector<int>, int> mem;
auto ask = [&](vector<int> v) {
// fill unknown places with unconfirmed numbers in order
int ind = 0;
auto q = p;
for (int i = 0; i < n; ++i) {
if (q[i] == -1) {
q[i] = v[ind];
++ind;
}
}
if (mem.count(q)) return mem[q];
int ans = query(q);
if (ans == n) exit(0);
return mem[q] = ans;
};
// make sure that nums[0] is on the wrong place
int s1 = ask(nums);
swap(nums[0], nums[1]);
int s2 = ask(nums);
if (s2 > s1)
swap(nums[0], nums[1]);
while (nums.size() > 2) {
vector<int> inds;
// keep index of first element of each pair to make code easier
for (int i = 1; i + 1 < nums.size(); i += 2) {
inds.pb(i);
}
int s1 = ask(nums);
for (int i = 0; i < inds.size(); ++i) {
int k = inds[i];
swap(nums[k], nums[k + 1]);
}
int s2 = ask(nums);
if (s1 == s2) {
// try again
for (int i = 1; i < nums.size(); ++i)
swap(nums[i], nums[rnd(i, nums.size() - 1)]);
continue;
}
if (s1 < s2) {
// if s1 > s2 then got a decrease, but was looking for an increase => swap initial and swapped (just don't swap back)
for (int i = 0; i < inds.size(); ++i) {
int k = inds[i];
swap(nums[k], nums[k + 1]);
}
}
int s0 = min(s1, s2);
queue<pair<pair<int, int>, int>> q;
vector<pair<int, int>> good;
vector<int> rem;
int dif = abs(s1 - s2);
q.emplace(mp(0, (int)inds.size() - 1), dif);
while (!q.empty()) {
auto [lr, dif] = q.front();
auto [l, r] = lr;
q.pop();
if (l == r) {
swap(nums[inds[l]], nums[inds[l] + 1]);
int s2 = ask(nums);
swap(nums[0], nums[inds[l]]);
int s3 = ask(nums);
swap(nums[0], nums[inds[l]]);
swap(nums[inds[l]], nums[inds[l] + 1]);
if (s3 < s2) {
// nums[inds[l]+1] should be on the place inds[l]
good.eb(inds[l], nums[inds[l] + 1]);
rem.pb(inds[l] + 1);
} else {
// nums[inds[l]] should be on the place inds[l]+1
good.eb(inds[l] + 1, nums[inds[l]]);
rem.pb(inds[l]);
}
continue;
}
int m = (l + r) / 2;
for (int i = l; i <= m; ++i)
swap(nums[inds[i]], nums[inds[i] + 1]);
int ss = ask(nums);
for (int i = l; i <= m; ++i)
swap(nums[inds[i]], nums[inds[i] + 1]);
int dif1 = ss - s0;
int dif2 = dif - dif1;
if (dif1 > 0)
q.emplace(mp(l, m), dif1);
if (dif2 > 0)
q.emplace(mp(m + 1, r), dif2);
}
// converting relative position in unconfirmed numbers to absolute position in the permutation
int pos = 0;
for (int i = 0; i < n; ++i) {
if (p[i] != -1) continue;
for (auto [a, b] : good) {
if (pos == a)
p[i] = b;
}
++pos;
}
// removing confirmed elements
sort(rem.begin(), rem.end());
reverse(rem.begin(), rem.end());
for (auto a : rem) {
nums.erase(nums.begin() + a);
}
}
if (nums.size() == 2)
swap(nums[0], nums[1]); // no need to check, because nums[0] is definitely on the wrong place
ask(nums);
assert(false);
}
Compilation message
mouse.cpp: In function 'void solve(int)':
mouse.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < nums.size(); ++i)
| ~~^~~~~~~~~~~~~
mouse.cpp:93:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 1; i + 1 < nums.size(); i += 2) {
| ~~~~~~^~~~~~~~~~~~~
mouse.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < inds.size(); ++i) {
| ~~^~~~~~~~~~~~~
mouse.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 1; i < nums.size(); ++i)
| ~~^~~~~~~~~~~~~
mouse.cpp:111:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < inds.size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 20 |
| 2 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 6 |
| 3 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 16 |
| 4 |
Correct |
1 ms |
640 KB |
Correct! Number of queries: 17 |
| 5 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 21 |
| 6 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 22 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 20 |
| 2 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 6 |
| 3 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 16 |
| 4 |
Correct |
1 ms |
640 KB |
Correct! Number of queries: 17 |
| 5 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 21 |
| 6 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 22 |
| 7 |
Correct |
6 ms |
364 KB |
Correct! Number of queries: 400 |
| 8 |
Correct |
6 ms |
364 KB |
Correct! Number of queries: 400 |
| 9 |
Correct |
5 ms |
364 KB |
Correct! Number of queries: 300 |
| 10 |
Correct |
5 ms |
364 KB |
Correct! Number of queries: 400 |
| 11 |
Correct |
5 ms |
364 KB |
Correct! Number of queries: 300 |
| 12 |
Correct |
6 ms |
364 KB |
Correct! Number of queries: 400 |
| 13 |
Correct |
4 ms |
380 KB |
Correct! Number of queries: 300 |
| 14 |
Correct |
9 ms |
364 KB |
Correct! Number of queries: 400 |
| 15 |
Correct |
7 ms |
364 KB |
Correct! Number of queries: 300 |
| 16 |
Correct |
6 ms |
492 KB |
Correct! Number of queries: 300 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 20 |
| 2 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 6 |
| 3 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 16 |
| 4 |
Correct |
1 ms |
640 KB |
Correct! Number of queries: 17 |
| 5 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 21 |
| 6 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 22 |
| 7 |
Correct |
6 ms |
364 KB |
Correct! Number of queries: 400 |
| 8 |
Correct |
6 ms |
364 KB |
Correct! Number of queries: 400 |
| 9 |
Correct |
5 ms |
364 KB |
Correct! Number of queries: 300 |
| 10 |
Correct |
5 ms |
364 KB |
Correct! Number of queries: 400 |
| 11 |
Correct |
5 ms |
364 KB |
Correct! Number of queries: 300 |
| 12 |
Correct |
6 ms |
364 KB |
Correct! Number of queries: 400 |
| 13 |
Correct |
4 ms |
380 KB |
Correct! Number of queries: 300 |
| 14 |
Correct |
9 ms |
364 KB |
Correct! Number of queries: 400 |
| 15 |
Correct |
7 ms |
364 KB |
Correct! Number of queries: 300 |
| 16 |
Correct |
6 ms |
492 KB |
Correct! Number of queries: 300 |
| 17 |
Correct |
105 ms |
2796 KB |
Correct! Number of queries: 2300 |
| 18 |
Correct |
91 ms |
2392 KB |
Correct! Number of queries: 2100 |
| 19 |
Correct |
93 ms |
2560 KB |
Correct! Number of queries: 2100 |
| 20 |
Correct |
107 ms |
2796 KB |
Correct! Number of queries: 2300 |
| 21 |
Correct |
104 ms |
2540 KB |
Correct! Number of queries: 2200 |
| 22 |
Correct |
103 ms |
2540 KB |
Correct! Number of queries: 2100 |
| 23 |
Correct |
103 ms |
2676 KB |
Correct! Number of queries: 2100 |
| 24 |
Correct |
103 ms |
2796 KB |
Correct! Number of queries: 2200 |
| 25 |
Correct |
110 ms |
2924 KB |
Correct! Number of queries: 2300 |
| 26 |
Correct |
121 ms |
2796 KB |
Correct! Number of queries: 2300 |
