Salve!
Sto provando a risolvere il problema Classifica senza fili usando Fenwick Tree ma, nonostante l’algoritmo riesca a risolvere i casi di esempio e la subtask 3, per tutti gli altri testcase fallisce miseramente. Controllando le assunzioni ipotizzo sia un problema legato all’uso di squalifica: il punto è che sto cercando controesempi da mezz’ora ma il programma, ai miei occhi, sembra risolverli tutti ! Forse ho capito male il problema o leggo male la traccia… Qualcuno può darmi qualche suggerimento (magari un controesempio, appunto)?
Codice:
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)
using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;
set<ii> classifica;
vi pos;
int n;
vi t;
void upd(int pos) {
for(int i = pos; i <= n; i += (i&-i)) {
t[i - 1]--;
}
}
int sum(int pos) {
int s = 0;
for(int i = pos; i > 0; i -= (i&-i)) {
s += t[i - 1];
}
return s;
}
void inizia(int N, int ids[]) {
pos.resize(N);
for(int i = 0; i < N; i++) {
classifica.insert({i + 1, ids[i]});
pos[ids[i]] = i + 1;
}
int sz = 1;
while(sz < N) sz *= 2;
t.resize(sz, 0);
n = N;
return;
}
int partecipante(int pos) {
pos -= sum(pos);
return classifica.lower_bound({pos, 0})->ss;
}
void supera(int id) {
int curr = pos[id] + sum(pos[id]), take = partecipante(curr - 1);
classifica.insert({pos[take], id});
classifica.insert({pos[id], take});
classifica.erase({pos[id], id});
classifica.erase({pos[take], take});
swap(pos[id], pos[take]);
}
void squalifica(int id) {
classifica.erase({pos[id], id});
upd(pos[id]);
}
Grazie! Ho modificato la funzione partecipante con questo obbrobrio
int partecipante(int pos) {
int last = 0;
while(sum(pos) != last) {
int tmp = sum(pos);
pos -= sum(pos) - last;
last = tmp;
}
return classifica.lower_bound({pos, 0})->ss;
}
il che mi permette di raccogliere un onesto 34/100.
E’ ovvio come gli altri testcase falliscano per via dell’elevata complessità computazionale.
La mia domanda però è: esiste un approccio in grado di risolvere questo problema con un BIT oppure devo ripiegare per forza sui Segment Tree?
Per quanto ne so, l’unica soluzione è con un segment tree. Forse è possibile risolverlo con un fenwick in \mathcal O(N\log^2 N) ma sarebbe comunque troppo lento.
Avevo provato con un segment tree solo che ottengo solo 16 punti
praticamente se uno viene eliminato al suo posto ci metto 1 e poi calcolo la somma in modo tale da ottenere la risposta per un indice a qui sommo la somma nel segmento da 0 a quel indice
int T[2000010];
int N1;
int S[2000010];
int L[2000010];
void add(int k, int s)
{
k+=N1;
T[k]+=s;
for(k/=2;k>=1;k/=2)
{
T[k] = T[2*k]+T[2*k+1];
}
}
int somma(int a,int b)
{
a+=N1;
b+=N1;
int s = 0;
while(a<=b)
{
if(a%2 == 1) s+=T[a++];
if(b%2 == 0) s+=T[b--];
a/=2;b/=2;
}
return s;
}
void inizia(int N, int ids[]) {
N1 = N;
for(int i = 0 ;i<2000010;i++)
{
T[i] = 0;
}
for(int i = 0;i<N;i++) {S[i] = ids[i]; L[S[i]] = i;}
return ;
}
void supera(int id) {
int a = L[id];
int b = S[a-1];
L[id] = a-1;
L[b] = a;
S[a-1] = id;
S[a] = b;
return ;
}
void squalifica(int id) {
add(L[id]-somma(0,L[id]),1);
return ;
}
int partecipante(int pos) {
int m = somma(0,pos-1);
int l = S[pos-1+m];
return l;
}
! Forse ho capito male il problema o leggo male la traccia… Qualcuno può darmi qualche suggerimento (magari un controesempio, appunto)?
)