Submission #1171926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171926		browntoad	Mouse (info1cup19_mouse)	C++20	100 / 100	45 ms	3040 KiB

mouse

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

// #define TOAD

#ifdef TOAD
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

#ifdef TOAD
int query(vector<int> pus){
	for (auto x:pus) cout<<x<<' ';
	cout<<endl<<flush;
	int in; cin>>in;
	return in;
}
#endif

vector<vector<pii>> round_robin(int N){ // 0-base
    vector<int> tmp(N);
    if (N&1) tmp.pb(0);
    iota(ALL(tmp), 0);
    if (N&1){
        tmp[N] = -1; // bye
    }

    int dnda = SZ(tmp);
    vector<vector<pii>> ret;
    REP(i, dnda-1){
        vector<pii> pp;
        REP(j, dnda/2){
            if (tmp[dnda-j-1] != -1){
                pp.pb({tmp[j], tmp[dnda-j-1]});
            }
        }
        ret.pb(pp);

        // shift
        int tval = tmp[0];
        REP(j, dnda-2){
            tmp[j] = tmp[j+1];
        }
        tmp[dnda-2] = tval;
    }
    return ret;
}

static vector<int> g[maxn];
void solve(int N){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	vector<int> derang(N);
	REP(i, N) derang[i] = i+1;

	if (N <= 2){
		if (N == 1){
			query(derang);
			return;
		}
		int ret = query(derang);
		if (ret == 0){
			swap(derang[0], derang[1]);
			query(derang);
		}
		return;
	}

	int ret;
	while(1){
        shuffle(ALL(derang), rng);
        ret = query(derang); if (ret == N) return;
        if (ret == 0) break;
	}
    vector<vector<pii>> robin = round_robin(N);

    vector<pii> e; // edges of the cycles, at most N
    for(auto vc:robin){
        int m = SZ(vc), ptr = 0;
        while(ptr < m){
            FOR(i, ptr, m) swap(derang[vc[i].f], derang[vc[i].s]);
            ret = query(derang); if (ret == N) return;
            FOR(i, ptr, m) swap(derang[vc[i].f], derang[vc[i].s]);
            if (ret == 0) break;
            // exists a pair that changes p
            int l = ptr, r = m-1;
            while(l < r){
                int mid = l+r>>1;
                FOR(i, ptr, mid+1) swap(derang[vc[i].f], derang[vc[i].s]);
                ret = query(derang); if (ret == N) return;
                FOR(i, ptr, mid+1) swap(derang[vc[i].f], derang[vc[i].s]);

                if (ret == 0){
                    l = mid+1;
                }
                else r = mid;
            }
            e.pb(vc[l]);
            ptr = l+1;
        }
    }

    for (auto pp:e){ // still 0-base
        g[pp.f].pb(pp.s);
        g[pp.s].pb(pp.f);
    }
    vector<bool> occ(N);

    int moo = 0;
    REP(i, N){
        if (occ[i]) continue;
        vector<int> cyc;
        int cur = i;
        do{
            occ[cur] = 1;
            cyc.pb(cur);

            bool fnd = 0;
            for (auto v:g[cur]){
                if (!occ[v]){
                    cur = v;
                    fnd = 1;
                    break;
                }
            }
            if (!fnd) break;
        }
        while(cur != i);

        if (SZ(cyc) == 2){
            swap(derang[cyc[0]], derang[cyc[1]]);
            moo += 2;
        }
        else{
            vector<int> tmpderang = derang;
            REP(j, SZ(cyc)){
                tmpderang[cyc[j]] = derang[cyc[(j+1)%SZ(cyc)]];
            }
            ret = query(tmpderang); if (ret == N) return;

            if (ret > moo){
                derang = tmpderang;
            }
            else{
                REP(j, SZ(cyc)){
                    tmpderang[cyc[j]] = derang[cyc[(j+SZ(cyc)-1)%SZ(cyc)]];
                }
                derang = tmpderang;
            }

            moo += SZ(cyc);
        }
    }
    assert(moo == N);

    query(derang);
}

#ifdef TOAD
signed main(){
	IOS();
	int n; cin>>n;
	round_robin(n);
	//cout<<n/0.63 * n/2<<endl;
	solve(n);
}
#endif

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49