Submission #365699

#	Time	Username	Problem	Language	Result	Execution time	Memory
365699		maksim1744	Mouse (info1cup19_mouse)	C++17	100 / 100	121 ms	2924 KiB

mouse

/*
    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 (stderr)

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) {
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49