This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
author: Maksim1744
created: 12.02.2021 00:39:20
*/
#include "bits/stdc++.h"
#ifndef HOUSE
#include "grader.h"
#endif
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
#ifdef HOUSE
vector<int> p = {1, 3, 2, 4, 5, 8, 7, 6};
// vector<int> p = {1, 3, 2, 4};
int cnt = 0;
int query(vector<int> q) {
++cnt;
assert(q.size() == p.size());
auto qq = q;
sort(qq.begin(), qq.end());
for (int i = 0; i < qq.size(); ++i) {
assert(qq[i] == i + 1);
}
int ans = 0;
for (int i = 0; i < p.size(); ++i) {
ans += (p[i] == q[i]);
}
// cout << q << "-> " << ans << endl;
if (ans == q.size()) {
cout << "done in " << cnt << " queries" << endl;
}
return ans;
}
#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;
set<int> unused_places, unused_numbers;
for (int i = 0; i < n; ++i) {
unused_places.insert(i);
unused_numbers.insert(i + 1);
}
auto ask = [&](vector<int> v) {
int ind = 0;
for (int i = 0; i < n; ++i) {
if (p[i] != -1) {
unused_places.erase(i);
unused_numbers.erase(p[i]);
}
}
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;
};
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) {
shows;
vector<int> inds;
for (int i = 1; i + 1 < nums.size(); i += 2) {
inds.pb(i);
}
show(p);
show(nums);
show(inds);
int s1 = ask(nums);
int R = inds.size() - 1;
// if (nums.size() > 128) R /= 2;
// R = min(R, 128);
for (int i = 0; i <= R; ++i) {
int k = inds[i];
swap(nums[k], nums[k + 1]);
}
int s2 = ask(nums);
if (s1 == s2) {
for (int i = 1; i < nums.size(); ++i)
swap(nums[i], nums[rnd(i, nums.size() - 1)]);
continue;
}
if (s1 < s2) {
for (int i = 0; i <= R; ++i) {
int k = inds[i];
swap(nums[k], nums[k + 1]);
}
}
show(nums);
int s0 = min(s1, s2);
show(s0);
queue<pair<pair<int, int>, int>> q;
vector<pair<int, int>> good;
vector<int> rem;
int dif = abs(s1 - s2);
q.emplace(mp(0, R), dif);
while (!q.empty()) {
auto [lr, dif] = q.front();
auto [l, r] = lr;
q.pop();
if (l == r) {
// int s1 = ask(nums);
swap(nums[inds[l]], nums[inds[l] + 1]);
int s2 = ask(nums);
// assert(s2 > s1);
swap(nums[0], nums[inds[l]]);
int s3 = ask(nums);
swap(nums[0], nums[inds[l]]);
swap(nums[inds[l]], nums[inds[l] + 1]);
show(s1, s2, s3);
show(nums, inds[l]);
if (s3 < s2) {
good.eb(inds[l], nums[inds[l] + 1]);
rem.pb(inds[l] + 1);
} else {
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);
}
int pos = 0;
show(good);
show(rem);
for (int i = 0; i < n; ++i) {
if (p[i] != -1) continue;
for (auto [a, b] : good) {
if (pos == a)
p[i] = b;
}
++pos;
}
sort(rem.begin(), rem.end());
reverse(rem.begin(), rem.end());
for (auto a : rem) {
nums.erase(nums.begin() + a);
}
// int l = 0, r = R;
// while (l != r) {
// int m = (l + r) / 2;
// for (int i = l; i <= m; ++i)
// swap(nums[inds[i]], nums[inds[i] + 1]);
// int ss = ask(nums);
// if (ss > s0)
// r = m;
// else
// l = m + 1;
// for (int i = l; i <= m; ++i)
// swap(nums[inds[i]], nums[inds[i] + 1]);
// }
// show(nums, l, r);
// swap(nums[inds[l]], nums[inds[l] + 1]);
// int was = ask(nums);
// int ind;
// if (was == s0 + 2) {
// ind = inds[l];
// int pos = 0;
// for (int i = 0; i < n; ++i) {
// if (p[i] != -1) continue;
// if (pos == ind)
// p[i] = nums[ind];
// if (pos == ind + 1)
// p[i] = nums[ind + 1];
// ++pos;
// }
// nums.erase(nums.begin() + ind);
// nums.erase(nums.begin() + ind);
// } else {
// swap(nums[0], nums[inds[l]]);
// int ss = ask(nums);
// swap(nums[0], nums[inds[l]]);
// if (ss < was)
// ind = inds[l];
// else
// ind = inds[l] + 1;
// int pos = 0;
// for (int i = 0; i < n; ++i) {
// if (p[i] != -1) continue;
// if (pos == ind)
// p[i] = nums[ind];
// ++pos;
// }
// nums.erase(nums.begin() + ind);
// }
}
// ask(nums);
if (nums.size() == 2)
swap(nums[0], nums[1]);
ask(nums);
assert(false);
}
#ifdef HOUSE
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
p.clear();
p.resize(256);
for (int i = 0; i < p.size(); ++i)
p[i] = i + 1;
for (int i = 0; i < p.size(); ++i)
swap(p[i], p[rnd(i, p.size() - 1)]);
sort(p.begin(), p.end());
reverse(p.begin(), p.end());
cout << "p: " << p << endl;
int n = p.size();
solve(n);
return 0;
}
#endif
Compilation message (stderr)
mouse.cpp: In function 'void solve(int)':
mouse.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < nums.size(); ++i)
| ~~^~~~~~~~~~~~~
mouse.cpp:47:23: warning: statement has no effect [-Wunused-value]
47 | #define shows 42
| ^~
mouse.cpp:127:9: note: in expansion of macro 'shows'
127 | shows;
| ^~~~~
mouse.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 1; i + 1 < nums.size(); i += 2) {
| ~~~~~~^~~~~~~~~~~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:132:9: note: in expansion of macro 'show'
132 | show(p);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:133:9: note: in expansion of macro 'show'
133 | show(nums);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:134:9: note: in expansion of macro 'show'
134 | show(inds);
| ^~~~
mouse.cpp:147:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int i = 1; i < nums.size(); ++i)
| ~~^~~~~~~~~~~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:157:9: note: in expansion of macro 'show'
157 | show(nums);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:159:9: note: in expansion of macro 'show'
159 | show(s0);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:178:17: note: in expansion of macro 'show'
178 | show(s1, s2, s3);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:179:17: note: in expansion of macro 'show'
179 | show(nums, inds[l]);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:204:9: note: in expansion of macro 'show'
204 | show(good);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:205:9: note: in expansion of macro 'show'
205 | show(rem);
| ^~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
