This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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?3050:n>7?450: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);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |