oj.uz

Submission #913200

# Submission time Handle Problem Language Result Execution time Memory
913200 2024-01-20T06:37:24 Z vjudge1 Mouse (info1cup19_mouse) C++17
100 / 100
 49 ms 700 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int MAXN = 300;

int val[MAXN], N;
bool mark[MAXN];

void rotate1(vector <int> mis,
vector <int> &per) {
    int ptr = 0, K = mis.size();
    for (int i = 0; i < N; i++)
        if (!val[i])
            per[i] = mis[++ptr % K];
        else per[i] = val[i];
}

void rotate2(vector <int> mis,
vector <int> &per, int cnt) {
    per[0] = mis[0];
    int ptr = 0, K = mis.size();
    for (int i = 1; i < N; i++)
        if (!val[i]) {
            if (ptr < cnt) {
                if (++ptr == cnt)
                    per[i] = val[0];
                else per[i] = mis[ptr % K];
            } else per[i] = mis[ptr++];
        } else per[i] = val[i];
}

void lock(vector <int> tmp,
vector <int> &mis, vector <int> &per) {
    rotate1(mis, per);
    for (int i : tmp)
        mark[mis[i]] = true;
    for (int i = 0; i < N; i++)
        if (!val[i] && mark[per[i]])
            val[i] = per[i];
    for (int i : tmp)
        mark[mis[i]] = false;
    mis.clear();
    for (int i = 0; i < N; i++) {
        if (!val[i])
            mis.push_back(per[i]);
    }
}

void solve(int N) {
    vector <int> per(::N = N);
    iota(per.begin(), per.end(), 1);
    int idx[] = {-1, -1};
    for (int i = 0; i < N; i++) {
        swap(per[i], per[0]);
        val[i] = query(per);
        if (val[i] == N) return;
        swap(per[i], per[0]);
        if (abs(val[i] - val[0]) == 2)
            break;
    }
    bool two = false;
    for (int i = 1; i < N; i++)
        if (val[i] - val[0] == 2) {
            swap(per[i], per[0]);
            two = true;
        } else if (val[0] - val[i] == -2)
            two = true;
    if (!two) {
        for (int i = 1; i < N; i++)
            if (val[i] - val[0] == 1)
                idx[idx[0] >= 0] = i;
        if (idx[1] >= 0) {
            vector <int> tmp, ans;
            tmp.push_back(1);
            tmp.push_back(idx[0] + 1);
            tmp.push_back(idx[1] + 1);
            sort(tmp.begin(), tmp.end());
            int cur = -1;
            do {
                per[0] = tmp[0];
                per[idx[0]] = tmp[1];
                per[idx[1]] = tmp[2];
                int nxt = query(per);
                if (nxt == N) return;
                if (nxt > cur) {
                    cur = nxt; ans = tmp;
                }
            } while (next_permutation
            (tmp.begin(), tmp.end()));
            per[0] = ans[0];
            per[idx[0]] = ans[1];
            per[idx[1]] = ans[2];
        } else if (idx[0] >= 0)
            swap(per[idx[0]], per[0]);
    }
    memset(val, 0, sizeof val);
    int cur = query(per);
    if (cur == N) return;
    val[0] = per[0];
    vector <int> mis;
    for (int i = 1; i < N; i++) {
        swap(per[i], per[0]);
        int nxt = query(per);
        if (nxt == N) return;
        if (cur - nxt == 2)
            val[i] = per[0];
        else mis.push_back(per[0]);
        swap(per[i], per[0]);
    }
    while (mis.size()) {
        rotate1(mis, per);
        int dif = query(per) - cur, ptr = 1;
        if (cur + dif == N) return;
        vector <int> tmp;
        for (int t = 0; t < dif; t++) {
            int lo = ptr + 1, hi = mis.size();
            ptr = 1;
            while (lo <= hi) {
                int mi = (lo + hi) / 2;
                rotate2(mis, per, mi);
                int nxt = query(per);
                if (nxt == N) return;
                if (nxt >= cur + t) {
                    ptr = mi; hi = mi - 1;
                } else lo = mi + 1;
            }
            tmp.push_back(ptr - 1);
        }
        cur += dif; lock(tmp, mis, per);
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 25
2 Correct 1 ms 344 KB Correct! Number of queries: 15
3 Correct 1 ms 344 KB Correct! Number of queries: 22
4 Correct 1 ms 344 KB Correct! Number of queries: 26
5 Correct 1 ms 344 KB Correct! Number of queries: 22
6 Correct 1 ms 500 KB Correct! Number of queries: 15

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 25
2 Correct 1 ms 344 KB Correct! Number of queries: 15
3 Correct 1 ms 344 KB Correct! Number of queries: 22
4 Correct 1 ms 344 KB Correct! Number of queries: 26
5 Correct 1 ms 344 KB Correct! Number of queries: 22
6 Correct 1 ms 500 KB Correct! Number of queries: 15
7 Correct 3 ms 504 KB Correct! Number of queries: 400
8 Correct 3 ms 504 KB Correct! Number of queries: 400
9 Correct 4 ms 344 KB Correct! Number of queries: 300
10 Correct 4 ms 364 KB Correct! Number of queries: 300
11 Correct 2 ms 344 KB Correct! Number of queries: 300
12 Correct 3 ms 344 KB Correct! Number of queries: 300
13 Correct 4 ms 344 KB Correct! Number of queries: 300
14 Correct 4 ms 344 KB Correct! Number of queries: 300
15 Correct 2 ms 344 KB Correct! Number of queries: 300
16 Correct 3 ms 344 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 25
2 Correct 1 ms 344 KB Correct! Number of queries: 15
3 Correct 1 ms 344 KB Correct! Number of queries: 22
4 Correct 1 ms 344 KB Correct! Number of queries: 26
5 Correct 1 ms 344 KB Correct! Number of queries: 22
6 Correct 1 ms 500 KB Correct! Number of queries: 15
7 Correct 3 ms 504 KB Correct! Number of queries: 400
8 Correct 3 ms 504 KB Correct! Number of queries: 400
9 Correct 4 ms 344 KB Correct! Number of queries: 300
10 Correct 4 ms 364 KB Correct! Number of queries: 300
11 Correct 2 ms 344 KB Correct! Number of queries: 300
12 Correct 3 ms 344 KB Correct! Number of queries: 300
13 Correct 4 ms 344 KB Correct! Number of queries: 300
14 Correct 4 ms 344 KB Correct! Number of queries: 300
15 Correct 2 ms 344 KB Correct! Number of queries: 300
16 Correct 3 ms 344 KB Correct! Number of queries: 300
17 Correct 47 ms 440 KB Correct! Number of queries: 2200
18 Correct 44 ms 692 KB Correct! Number of queries: 2100
19 Correct 45 ms 680 KB Correct! Number of queries: 2100
20 Correct 47 ms 696 KB Correct! Number of queries: 2200
21 Correct 45 ms 444 KB Correct! Number of queries: 2100
22 Correct 48 ms 440 KB Correct! Number of queries: 2100
23 Correct 49 ms 696 KB Correct! Number of queries: 2100
24 Correct 45 ms 700 KB Correct! Number of queries: 2200
25 Correct 46 ms 684 KB Correct! Number of queries: 2200
26 Correct 47 ms 696 KB Correct! Number of queries: 2200