Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: permutazione2.
Effettuiamo una binary search per trovare la posizione di ogni elemento della permutazione. Questa soluzione richiede query di tipo , query di tipo e query di tipo , quindi risolve i subtask e .
Come ridurre le query di tipo e ?
È possibile effettuare le binary search in parallelo.
Spiegazione dell'algoritmo: parallel binary search.
Questa soluzione richiede query di tipo , query di tipo e query di tipo , quindi risolve i subtask , , , e .
Per risolvere il subtask , dobbiamo ridurre ulteriormente le query di tipo , eventualmente aumentando quelle di tipo .
È possibile farlo dividendo l'intervallo delle binary search, invece che in parti, in parti.
Per evitare di effettuare troppe query di tipo , bisogna interrompere le query chiedi(x) non appena è stato trovato l'intervallo in cui si trova .
Questa soluzione richiede query di tipo , query di tipo e query di tipo , quindi risolve il subtask .
Subtask , , , ,
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define maxn 1010
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll rp, bsl[maxn], bsa[maxn], bsb[maxn], bsu[maxn];
ll st, cr;
vector<ll> adj[maxn];
bool chiedi(int K);
void stato();
void sposta();
void indovina(int N, int A, int B, int C, int H[]) {
n = N; st = 1; cr = 0;
for (i = 0; i < n; i++) {
bsl[i] = 0; bsu[i] = n;
}
for (rp = 1; rp <= 10; rp++) {
for (i = 0; i < n; i++) adj[i].clear();
for (i = 0; i < n; i++) {
if (bsl[i] == bsu[i]) continue;
bsa[i] = bsl[i]; bsb[i] = (bsl[i] + bsu[i]) / 2;
adj[bsb[i]].pb(i);
}
while (true) {
for (auto u : adj[cr]) {
if (chiedi(u)) {
bsu[u] = bsb[u];
} else {
bsl[u] = bsb[u] + 1;
}
}
if (cr + st == -1 || cr + st == n) break;
sposta(); cr += st;
}
stato(); st = -st;
}
for (i = 0; i < n; i++) H[bsl[i]] = i;
}
Subtask
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define maxn 1010
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll rp, bsl[maxn], bsu[maxn];
ll st, cr, sq, step;
bool vis[maxn];
vector<ll> bsm[maxn];
vector<array<ll, 2>> adj[maxn];
bool chiedi(int K);
void stato();
void sposta();
void indovina(int N, int A, int B, int C, int H[]) {
n = N; st = 1; cr = 0; sq = sqrt(n);
for (i = 0; i < n; i++) {
bsl[i] = 0; bsu[i] = n;
}
for (rp = 1; rp <= 2; rp++) {
if (rp == 1) step = sq;
else step = 1;
for (i = 0; i < n; i++) {
adj[i].clear(); bsm[i].clear();
}
for (i = 0; i < n; i++) {
if (bsl[i] == bsu[i]) continue;
bsm[i].pb(bsl[i] - 1);
for (j = bsl[i] + step - 1; j < bsu[i]; j += step) {
bsm[i].pb(j); adj[j].pb({i, (j - bsl[i] + 1) / step});
}
bsm[i].pb(bsu[i]);
}
for (i = 0; i < n; i++) vis[i] = false;
while (true) {
for (auto [u, p] : adj[cr]) {
if (vis[u]) continue;
if (st == 1) {
if (chiedi(u)) {
bsl[u] = bsm[u][p - 1] + 1; bsu[u] = bsm[u][p]; vis[u] = true;
} else if (cr + step >= bsu[u]) {
bsl[u] = bsm[u][p] + 1;
}
} else {
if (!chiedi(u)) {
bsl[u] = bsm[u][p] + 1; bsu[u] = bsm[u][p + 1]; vis[u] = true;
} else if (cr - step <= bsl[u]) {
bsu[u] = bsm[u][p];
}
}
}
if (cr + st == -1 || cr + st == n) break;
sposta(); cr += st;
}
if (rp != 2) {
stato(); st = -st;
}
}
for (i = 0; i < n; i++) H[bsl[i]] = i;
}