Submission #930860

#	Time	Username	Problem	Language	Result	Execution time	Memory
930860		Tuanlinh123	Mouse (info1cup19_mouse)	C++17	91.62 / 100	83 ms	704 KiB

mouse

#include "grader.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(ll n) 
{
    ll q=n>50?3000:n>7?399:49, turn=-1, answered=0;
    vector <ll> crr(n);
    vector <vector <ll>> p(n+1, vector <ll> (n+1, 1));
    auto ask=[&](vector <ll> a, bool track)
    {
        if (answered) return n;
        if (track)
        {
            ll cnt=0;
            for (ll j=0; j<n; j++)
                cnt+=p[j+1][crr[j]];
            if (!cnt) {turn--; return 0;}
        }
        ll q=query(a);
        if (q==n) answered=1;
        return q;
    };
    while (turn+1<q)
    {
        turn++;
        if (turn%n==0)
        {
            iota(crr.begin(), crr.end(), 1);
            shuffle(crr.begin(), crr.end(), rng);
        }
        else rotate(crr.begin(), crr.begin()+1, crr.end());
        if (!ask(crr, 1)) for (ll j=0; j<n; j++) p[j+1][crr[j]]=0;
    }
    vector <ll> ans(n, 0), deg(n+1, 0);
    for (ll i=1; i<=n; i++)
        for (ll j=1; j<=n; j++)
            deg[i]+=p[i][j];
    function<void(ll)> backtrack=[&](ll id)
    {
        if (id==n) {ask(ans, 0); return;}
        pll best={n, 0};
        for (ll i=1; i<=n; i++)
            if (deg[i]>0) best=min(best, {deg[i], i});
        if (best.se==0) return;
        ll c=best.se; deg[c]=0;
        for (ll i=1; i<=n; i++)
        {
            if (!p[c][i]) continue;
            vector <ll> er;
            for (ll j=1; j<=n; j++)
                if (p[j][i]) p[j][i]=0, deg[j]--, er.pb(j);
            ans[c-1]=i, backtrack(id+1);
            for (ll j:er) p[j][i]=1, deg[j]++;
        }
        deg[c]=best.fi;
    }; backtrack(0);
}

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