# Aiuto con "Classifica senza fili"

**URL:** <https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249>\
**Category:** Aiuto\
**Created:** [23 Luglio 2020, 9:40am UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249 "2020-07-23T09:40:35Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![whothat](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/w/f19dbf/32.png) [@whothat](https://forum.olinfo.it/u/whothat)\
**Post date:** [23 Luglio 2020, 9:40am UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/1 "2020-07-23T09:40:35Z")

</div>

Salve!  
Sto provando a risolvere il problema [Classifica senza fili](https://training.olinfo.it/#/task/oii_classifica/statement) 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:

```auto
    #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]);
    }

```

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [23 Luglio 2020, 12:18pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/2 "2020-07-23T12:18:24Z")

</div>

Ciao, ecco un esempio in cui il tuo codice sbaglia:

```auto
7 4
0 1 2 3 4 5 6
x 0
x 2
x 4
p 4

```

Il tuo codice stampa 5, la risposta corretta è invece 6.

---

<div class="post-metadata">

**Author:** ![whothat](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/w/f19dbf/32.png) [@whothat](https://forum.olinfo.it/u/whothat)\
**Post date:** [23 Luglio 2020, 1:25pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/3 "2020-07-23T13:25:40Z")

</div>

Grazie! Ho modificato la funzione partecipante con questo obbrobrio

```auto
  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?

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [23 Luglio 2020, 1:34pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/4 "2020-07-23T13:34:58Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [23 Luglio 2020, 6:11pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/5 "2020-07-23T18:11:13Z")

</div>

Be’ in realtà puoi fare [lower bound](https://codeforces.com/blog/entry/61364) su un fenwick anche in logN (next quarantraining spoiler? 🌚)

---

<div class="post-metadata">

**Author:** ![bananamaths](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/ce7236/32.png) [@bananamaths](https://forum.olinfo.it/u/bananamaths)\
**Post date:** [29 Luglio 2020, 2:14pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/6 "2020-07-29T14:14:07Z")

</div>

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![bananamaths](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/ce7236/32.png) [@bananamaths](https://forum.olinfo.it/u/bananamaths)\
**Post date:** [29 Luglio 2020, 2:19pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/7 "2020-07-29T14:19:37Z")

</div>

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

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [31 Luglio 2020, 12:41pm UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/8 "2020-07-31T12:41:01Z")

</div>

@bananamaths ecco un esempio in cui il tuo codice sbaglia:

```auto
3 3
0 1 2
x 1
s 2
p 2

```

---

<div class="post-metadata">

**Author:** ![bananamaths](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/ce7236/32.png) [@bananamaths](https://forum.olinfo.it/u/bananamaths)\
**Post date:** [2 Agosto 2020, 9:17am UTC](https://forum.olinfo.it/t/aiuto-con-classifica-senza-fili/6249/9 "2020-08-02T09:17:28Z")

</div>

ah grazie! la funzione squalifica è quella che non va bene