Submission #413809

#	Time	Username	Problem	Language	Result	Execution time	Memory
413809		lyc	Mouse (info1cup19_mouse)	C++14	100 / 100	77 ms	328 KiB

mouse

#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 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49