oj.uz

Submission #950365

# Submission time Handle Problem Language Result Execution time Memory
950365 2024-03-20T08:51:39 Z Pring Mouse (info1cup19_mouse) C++17
39.3333 / 100
 101 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 260;
int n;
bitset<MXN> b;
int a[MXN][MXN];
vector<int> p;
vector<int> ans;

#ifndef MIKU
#include "grader.h"
#endif

#ifdef MIKU
int query(vector<int> v) {
    for (auto &i : v) cout << i << ' ';
    cout << endl;
    // cout << "5 3 7 1 6 2 4" << endl;
    int x;
    cin >> x;
    return x;
}
#endif

int ccc = 0;

int QUERY(vector<int> v) {
    int x = query(v);
    // assert(++ccc == 5040);
    if (x == n) exit(0);
    return x;
}

vector<int> ept() {
    vector<int> v;
    FOR(i, 0, n) if (!b[i]) v.push_back(i);
    return v;
}

void SET(int c) {
    vector<int> v = ept();
    // cout << "v: ";
    // for (auto &i : v) cout << i << ' ';
    // cout << endl;
    int x = v[0];
    vector<int> w(v.size());
    FOR(i, 1, v.size()) {
        swap(p[v[0]], p[v[i]]);
        w[i] = QUERY(p) - c;
        swap(p[v[0]], p[v[i]]);
    }
    if (*max_element(w.begin() + 1, w.end()) == *min_element(w.begin() + 1, w.end())) {
        ans[0] = p[v[0]];
        b[v[0]] = true;
        return;
    }
    x = *min_element(w.begin() + 1, w.end());
    FOR(i, 1, w.size()) if (w[i] == x) {
        ans[v[i]] = p[v[i]];
        b[v[i]] = true;
    }
    if (x == -2) {
        ans[0] = p[v[0]];
        b[v[0]] = true;
    }
}

void ROTATE(vector<int> &v, int c) {
    vector<int> w(v.size());
    FOR(i, 0, v.size()) w[i] = p[v[i]];
    rotate(w.begin(), w.begin() + c, w.end());
    FOR(i, 0, v.size()) p[v[i]] = w[i];
}

void calc(int s) {
    vector<int> v = ept();
    // cout << "calc v: ";
    // for (auto &i : v) cout << i << ' ';
    // cout << endl;
    vector<pii> w;
    ROTATE(v, 1);
    FOR(i, 1, v.size()) {
        w.emplace_back(QUERY(p) - s, i);
        ROTATE(v, 1);
    }
    auto [x, y] = *max_element(w.begin(), w.end());
    ROTATE(v, y);
    SET(x);
}

void solve(int _n) {
    if (_n == 1) {
        query(vector<int>{1});
        return;
    }
    n = _n;
    FOR(i, 0, n) b[i] = false;
    p.resize(n);
    ans.resize(n);
    vector<pii> v;
    FOR(i, 0, n) p[i] = i + 1;
    FOR(i, 0, n) {
        v.emplace_back(QUERY(p), i);
        rotate(p.begin(), p.begin() + 1, p.end());
    }
    auto [x, y] = *max_element(v.begin(), v.end());
    rotate(p.begin(), p.begin() + y, p.end());
    SET(x);
    int pre = b.count();
    while (b.count() < n) {
        calc(b.count());
        if (pre == b.count()) assert(false);
        pre = b.count();
    }
}

#ifdef MIKU
int32_t main() {
    int n;
    cin >> n;
    solve(n);
}
#endif

Compilation message

mouse.cpp: In function 'void solve(int)':
mouse.cpp:118:22: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |     while (b.count() < n) {
      |            ~~~~~~~~~~^~~
mouse.cpp:120:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if (pre == b.count()) assert(false);
      |             ~~~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 22
2 Correct 0 ms 344 KB Correct! Number of queries: 8
3 Correct 1 ms 344 KB Correct! Number of queries: 12
4 Correct 0 ms 344 KB Correct! Number of queries: 23
5 Correct 1 ms 344 KB Correct! Number of queries: 23
6 Correct 1 ms 344 KB Correct! Number of queries: 24

Subtask #2
26.333316 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 22
2 Correct 0 ms 344 KB Correct! Number of queries: 8
3 Correct 1 ms 344 KB Correct! Number of queries: 12
4 Correct 0 ms 344 KB Correct! Number of queries: 23
5 Correct 1 ms 344 KB Correct! Number of queries: 23
6 Correct 1 ms 344 KB Correct! Number of queries: 24
7 Correct 6 ms 440 KB Correct! Number of queries: 900
8 Correct 7 ms 444 KB Correct! Number of queries: 900
9 Correct 9 ms 600 KB Correct! Number of queries: 700
10 Correct 6 ms 436 KB Correct! Number of queries: 800
11 Correct 4 ms 444 KB Correct! Number of queries: 600
12 Correct 7 ms 440 KB Correct! Number of queries: 800
13 Correct 5 ms 444 KB Correct! Number of queries: 700
14 Correct 5 ms 440 KB Correct! Number of queries: 700
15 Correct 5 ms 440 KB Correct! Number of queries: 700
16 Correct 7 ms 444 KB Correct! Number of queries: 800

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 22
2 Correct 0 ms 344 KB Correct! Number of queries: 8
3 Correct 1 ms 344 KB Correct! Number of queries: 12
4 Correct 0 ms 344 KB Correct! Number of queries: 23
5 Correct 1 ms 344 KB Correct! Number of queries: 23
6 Correct 1 ms 344 KB Correct! Number of queries: 24
7 Correct 6 ms 440 KB Correct! Number of queries: 900
8 Correct 7 ms 444 KB Correct! Number of queries: 900
9 Correct 9 ms 600 KB Correct! Number of queries: 700
10 Correct 6 ms 436 KB Correct! Number of queries: 800
11 Correct 4 ms 444 KB Correct! Number of queries: 600
12 Correct 7 ms 440 KB Correct! Number of queries: 800
13 Correct 5 ms 444 KB Correct! Number of queries: 700
14 Correct 5 ms 440 KB Correct! Number of queries: 700
15 Correct 5 ms 440 KB Correct! Number of queries: 700
16 Correct 7 ms 444 KB Correct! Number of queries: 800
17 Runtime error 101 ms 448 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -