oj.uz

Submission #365604

# Submission time Handle Problem Language Result Execution time Memory
365604 2021-02-11T23:53:05 Z maksim1744 Mouse (info1cup19_mouse) C++17
99.2308 / 100
 136 ms 3180 KB 
/*
    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);

        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);
        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

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:146:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             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:156:9: note: in expansion of macro 'show'
  156 |         show(nums);
      |         ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
   45 | #define show(...)     42
      |                       ^~
mouse.cpp:158:9: note: in expansion of macro 'show'
  158 |         show(s0);
      |         ^~~~
mouse.cpp:45:23: warning: statement has no effect [-Wunused-value]
   45 | #define show(...)     42
      |                       ^~
mouse.cpp:172:9: note: in expansion of macro 'show'
  172 |         show(nums, l, r);
      |         ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Correct! Number of queries: 25
2 Correct 0 ms 364 KB Correct! Number of queries: 6
3 Correct 1 ms 364 KB Correct! Number of queries: 16
4 Correct 1 ms 364 KB Correct! Number of queries: 11
5 Correct 1 ms 364 KB Correct! Number of queries: 24
6 Correct 1 ms 364 KB Correct! Number of queries: 19

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Correct! Number of queries: 25
2 Correct 0 ms 364 KB Correct! Number of queries: 6
3 Correct 1 ms 364 KB Correct! Number of queries: 16
4 Correct 1 ms 364 KB Correct! Number of queries: 11
5 Correct 1 ms 364 KB Correct! Number of queries: 24
6 Correct 1 ms 364 KB Correct! Number of queries: 19
7 Correct 8 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: 400
10 Correct 8 ms 364 KB Correct! Number of queries: 400
11 Correct 5 ms 364 KB Correct! Number of queries: 300
12 Correct 8 ms 364 KB Correct! Number of queries: 400
13 Correct 7 ms 364 KB Correct! Number of queries: 300
14 Correct 8 ms 384 KB Correct! Number of queries: 400
15 Correct 7 ms 364 KB Correct! Number of queries: 400
16 Correct 8 ms 364 KB Correct! Number of queries: 400

Subtask #3
48.230749 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Correct! Number of queries: 25
2 Correct 0 ms 364 KB Correct! Number of queries: 6
3 Correct 1 ms 364 KB Correct! Number of queries: 16
4 Correct 1 ms 364 KB Correct! Number of queries: 11
5 Correct 1 ms 364 KB Correct! Number of queries: 24
6 Correct 1 ms 364 KB Correct! Number of queries: 19
7 Correct 8 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: 400
10 Correct 8 ms 364 KB Correct! Number of queries: 400
11 Correct 5 ms 364 KB Correct! Number of queries: 300
12 Correct 8 ms 364 KB Correct! Number of queries: 400
13 Correct 7 ms 364 KB Correct! Number of queries: 300
14 Correct 8 ms 384 KB Correct! Number of queries: 400
15 Correct 7 ms 364 KB Correct! Number of queries: 400
16 Correct 8 ms 364 KB Correct! Number of queries: 400
17 Correct 132 ms 3052 KB Correct! Number of queries: 2500
18 Correct 119 ms 2928 KB Correct! Number of queries: 2300
19 Correct 117 ms 2712 KB Correct! Number of queries: 2300
20 Correct 127 ms 3180 KB Correct! Number of queries: 2400
21 Correct 122 ms 2796 KB Correct! Number of queries: 2300
22 Correct 112 ms 2796 KB Correct! Number of queries: 2300
23 Correct 119 ms 2924 KB Correct! Number of queries: 2300
24 Correct 136 ms 3052 KB Correct! Number of queries: 2400
25 Correct 134 ms 3180 KB Correct! Number of queries: 2500
26 Correct 132 ms 2924 KB Correct! Number of queries: 2400