oj.uz

Submission #413809

# Submission time Handle Problem Language Result Execution time Memory
413809 2021-05-29T14:18:29 Z lyc Mouse (info1cup19_mouse) C++14
100 / 100
 77 ms 328 KB 
#include "grader.h"

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

int N;
vector<int> al[257], guess, cyc;
bool flag, vis[257];

void dfs(int i) {
    vis[i] = 1;
    cyc.push_back(i);
    for (int& v : al[i]) if (!vis[v]) dfs(v);
}

int qry() {
    int q = query(guess);
    flag = (q == N);
    return q;
}

int rqry(int s, int e, vector<int>& r) {
    FOR(i,s,e) if (r[i] != -1 && r[SZ(r)-1-i] != -1) {
        swap(guess[r[i]],guess[r[SZ(r)-1-i]]);
    }
    int q = qry();
    FOR(i,s,e) if (r[i] != -1 && r[SZ(r)-1-i] != -1) {
        swap(guess[r[i]],guess[r[SZ(r)-1-i]]);
    }
    return q;
}

void dnc(int s, int e, int v, vector<int>& r) {
    if (flag || !v) return;
    if (s == e) {
        al[r[s]].push_back(r[SZ(r)-1-s]);
        al[r[SZ(r)-1-s]].push_back(r[s]);
        return;
    }

    int m = (s+e)/2;

    int q = rqry(s,m,r);
    dnc(s,m,q,r);
    dnc(m+1,e,v-q,r);
}

void solve(int _N) {
    N = _N;

    guess.resize(N);
    iota(ALL(guess),1);

    while (query(guess)) random_shuffle(ALL(guess)); // ~ O(N) ?
    //for(int&v:guess){cout << v << ' ';} cout << endl;

    vector<int> r(N);
    iota(ALL(r),0);
    if (N&1) r.push_back(-1);
    FOR(i,1,N){
        //FOR(j,0,SZ(r)/2-1){ cout << r[j] << "," << r[SZ(r)-1-j] << " "; } cout << endl;
        int q = rqry(0,SZ(r)/2-1,r);
        if (flag) return;
        dnc(0,N-1,q,r);
        rotate(r.begin()+1,r.begin()+2,r.end());
    }

    memset(vis,0,sizeof vis);
    int p = 0;
    FOR(i,0,N-1) if (!vis[i]) {
        cyc.clear();

        dfs(i);
        FOR(i,0,SZ(cyc)-2) swap(guess[cyc[i]],guess[cyc[i+1]]);
        int q = qry();
        if (flag) return;

        if (q == p) {
            RFOR(i,SZ(cyc)-2,0) swap(guess[cyc[i]],guess[cyc[i+1]]);
            RFOR(i,SZ(cyc)-2,0) swap(guess[cyc[i]],guess[cyc[i+1]]);
            q += SZ(cyc);
        }
        p = q;
    }

    //for(int&v:guess){cout << v << ' ';} cout << endl;
    qry();
    assert(flag);

    return;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 23
2 Correct 1 ms 200 KB Correct! Number of queries: 13
3 Correct 1 ms 200 KB Correct! Number of queries: 18
4 Correct 1 ms 200 KB Correct! Number of queries: 22
5 Correct 1 ms 200 KB Correct! Number of queries: 26
6 Correct 1 ms 200 KB Correct! Number of queries: 35

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 23
2 Correct 1 ms 200 KB Correct! Number of queries: 13
3 Correct 1 ms 200 KB Correct! Number of queries: 18
4 Correct 1 ms 200 KB Correct! Number of queries: 22
5 Correct 1 ms 200 KB Correct! Number of queries: 26
6 Correct 1 ms 200 KB Correct! Number of queries: 35
7 Correct 6 ms 200 KB Correct! Number of queries: 300
8 Correct 5 ms 200 KB Correct! Number of queries: 300
9 Correct 6 ms 200 KB Correct! Number of queries: 300
10 Correct 6 ms 204 KB Correct! Number of queries: 300
11 Correct 4 ms 300 KB Correct! Number of queries: 300
12 Correct 6 ms 328 KB Correct! Number of queries: 300
13 Correct 6 ms 200 KB Correct! Number of queries: 300
14 Correct 5 ms 304 KB Correct! Number of queries: 300
15 Correct 7 ms 200 KB Correct! Number of queries: 300
16 Correct 6 ms 328 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 23
2 Correct 1 ms 200 KB Correct! Number of queries: 13
3 Correct 1 ms 200 KB Correct! Number of queries: 18
4 Correct 1 ms 200 KB Correct! Number of queries: 22
5 Correct 1 ms 200 KB Correct! Number of queries: 26
6 Correct 1 ms 200 KB Correct! Number of queries: 35
7 Correct 6 ms 200 KB Correct! Number of queries: 300
8 Correct 5 ms 200 KB Correct! Number of queries: 300
9 Correct 6 ms 200 KB Correct! Number of queries: 300
10 Correct 6 ms 204 KB Correct! Number of queries: 300
11 Correct 4 ms 300 KB Correct! Number of queries: 300
12 Correct 6 ms 328 KB Correct! Number of queries: 300
13 Correct 6 ms 200 KB Correct! Number of queries: 300
14 Correct 5 ms 304 KB Correct! Number of queries: 300
15 Correct 7 ms 200 KB Correct! Number of queries: 300
16 Correct 6 ms 328 KB Correct! Number of queries: 300
17 Correct 72 ms 300 KB Correct! Number of queries: 2000
18 Correct 61 ms 284 KB Correct! Number of queries: 2000
19 Correct 72 ms 320 KB Correct! Number of queries: 2000
20 Correct 73 ms 304 KB Correct! Number of queries: 2000
21 Correct 76 ms 200 KB Correct! Number of queries: 2000
22 Correct 71 ms 300 KB Correct! Number of queries: 2000
23 Correct 77 ms 296 KB Correct! Number of queries: 2000
24 Correct 74 ms 300 KB Correct! Number of queries: 2100
25 Correct 77 ms 280 KB Correct! Number of queries: 2100
26 Correct 76 ms 200 KB Correct! Number of queries: 2000