/*
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};
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);
for (auto k : inds) {
swap(nums[k], nums[k + 1]);
}
int s2 = ask(nums);
if (s1 == s2) {
nums.pb(nums[1]);
nums.erase(nums.begin() + 1);
// for (int i = 1; i < nums.size(); ++i)
// swap(nums[i], nums[rnd(i, nums.size() - 1)]);
continue;
}
if (s1 < s2) {
for (auto k : inds) {
swap(nums[k], nums[k + 1]);
}
}
show(nums);
int s0 = min(s1, s2);
show(s0);
int l = 0, r = (int)inds.size() - 1;
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
mouse.cpp: In function 'void solve(int)':
mouse.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | 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:126:9: note: in expansion of macro 'shows'
126 | shows;
| ^~~~~
mouse.cpp:128:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | 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:131:9: note: in expansion of macro 'show'
131 | show(p);
| ^~~~
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(nums);
| ^~~~
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(inds);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:151:9: note: in expansion of macro 'show'
151 | show(nums);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:153:9: note: in expansion of macro 'show'
153 | show(s0);
| ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
45 | #define show(...) 42
| ^~
mouse.cpp:167:9: note: in expansion of macro 'show'
167 | show(nums, l, r);
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 22 |
| 2 |
Correct |
0 ms |
364 KB |
Correct! Number of queries: 6 |
| 3 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 12 |
| 4 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 13 |
| 5 |
Execution timed out |
3052 ms |
364 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 22 |
| 2 |
Correct |
0 ms |
364 KB |
Correct! Number of queries: 6 |
| 3 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 12 |
| 4 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 13 |
| 5 |
Execution timed out |
3052 ms |
364 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 22 |
| 2 |
Correct |
0 ms |
364 KB |
Correct! Number of queries: 6 |
| 3 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 12 |
| 4 |
Correct |
1 ms |
364 KB |
Correct! Number of queries: 13 |
| 5 |
Execution timed out |
3052 ms |
364 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
