Hola buenas, vuelvo a escribir acá por otro problema del envío 5 (espero estar publicando en la sección correcta).
Esta vez es por el problema “aventureros”. Lo intenté resolver pero tengo un par de problemas. Esto es lo que traté de hacer:
La idea es calcular cuántas personas fueron eliminadas dentro del rango entre mi posición actual pos y mi posición actual más la longitud del salto (pos + L). Esto lo hago con un Fenwick Tree que setea en 1 las posiciones correspondientes a personas eliminadas, y obtiene la suma de todos los ‘1s’ dentro del rango que mencioné recién.
Primero me fijo si hacer ese salto excede la longitud de la fila de personas. Si es así, hago dos queries separadas: una entre mi posición de la fila y el final:
query(pos,N)
…y otra entre el principio de la fila y la posición en la que hubiera quedado en módulo N (siendo N la cantidad de personas original):
query2 ( 0 , (pos+C)%N )
A la suma de estas dos queries la multiplico por la parte entera de dividir la posición en la que hubiera quedado por N:
(query2 * floor( (pos+C) / N )
…por si “da varias vueltas”.
Mi nueva cantidad de saltos va a ser la suma de los resultados de esas dos queries y la cantidad de saltos original. Mi nueva posición va a ser la suma de todo lo anterior y mi posición original, todo en módulo N.
El problema viene ahora: ¿Qué pasa si caigo en una posición en la que la persona ya fue eliminada? Lo que me se me ocurre es pasar a la siguiente posición hasta encontrar una persona, pero tiene que haber una solución mejor.
Dejo mi código con esta solución fea (que encima tira seg fault en muchos casos):
Código
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#define forn(i,N) for(int i=0;i<N;i++)
using namespace std;
int N;
int maxN = 2<<15;
int pos=0;
int fenTree[100000]; /// jumps
int eliminado[100000];
queue <int> queries;
void pointUpdate( int x, int v ){
for (int i=x; i<maxN; i += i & -i){
fenTree[i] += v;
}
}
int rangeQuery( int x ){
int v=0;
for (int i=x; i; i -= i & -i){
v+=fenTree[i];
}
return v;
}
void processJump( int j ){
int newPos = pos+j, newJumps = 0;
int firstQuery = 0, secondQuery = 0;
if (newPos >= N){
firstQuery = rangeQuery(N) - rangeQuery(pos);
secondQuery = rangeQuery (newPos%N);
newJumps = (firstQuery + secondQuery) * floor(newPos/N);
} else {
newJumps = rangeQuery ( newPos ) - rangeQuery (pos);
}
newPos = (newPos + newJumps)%N;
while (eliminado[newPos]){
newPos = (newPos + 1)%N;
}
pointUpdate(newPos+1,1);
eliminado[newPos] = 1;
pos = newPos+1;
cout << pos << " ";
}
void processQueries(){
while (queries.size()){
int q = queries.front();
queries.pop();
processJump( q );
}
}
int main(){
//freopen("aventureros.txt","r",stdin);
freopen("aventureros.in","r",stdin);
freopen("aventureros.out","w",stdout);
cin >> N;
int buffQ;
forn(i,N-1){
cin >> buffQ;
queries.push(buffQ);
}
processQueries();
forn(i,N){
if (!eliminado[i]){
cout << endl << i+1 << endl;
break;
}
}
return 0;
}
Puede ser también que las queries al fenwick tree no tengan que estar indexadas en 0 sino en 1, pero de ambas formas el resultado es el mismo en el juez.
Ambos casos ejemplo me dan bien, pero al evaluador no le gusta para nada. Quisiera saber qué puedo hacer para solucionar esos casos (y si puede ser también dónde estoy accediendo a una dirección de memoria que no debería).
Muchas gracias!
