A mi también me interesa mucho la algoritmia y de hecho cuando surge algún tema relacionado en el foro suelo intentar ayudar.

También tengo bastantes problemas de jueces online resueltos, especialmente de UVa, Codeforces, Timus, SGU y Live Archive y participo con mi universidad en el ICPC, además de a título individual en otros concursos como el Google Code Jam o en el mismo Codeforces.

Sin embargo, no veo mucha actividad del tema en el foro. No sé hasta qué punto sería útil un subforo si la gente no muestra demasiado interés por el tema.

Esa opción es demasiado lenta. No se si estarás puesto en complejidad, pero vamos a analizar la de ese algoritmo. Voy a asumir que comparar strings se hace en tiempo constante, cosa que tampoco es cierta, pero no es lo que limita la velocidad.

Para cada palabra de la entrada (n en total) buscas en un vector de las palabras que han salido anteriormente dicha palabra. Supongamos que lees la palabra i-ésima. En caso peor, en el vector de palabras tendrás i - 1 palabras (es decir, hasta ahora todas son diferentes). En el peor de los casos, la nueva palabra no estará tampoco, por lo tanto harás i - 1 comparaciones. Consideremos entonces las comparaciones que harás en caso peor: 0 la primera palabra, 1 la segunda, 2 la tercera, ..., n - 1 la última. Esto suma n(n - 1)/2, que asintóticamente (muy informalmente significa considerando sólo la mayor potencia e ignorando la constante que la multiplica) es equivalente a n².

En el enunciado te dicen que n es como mucho 10⁵ (las restricciones de la entrada son casi lo más importante en un problema de programación, debes tenerlas muy en cuenta y si pides ayuda dilas también). Por lo tanto, con ese algoritmo serían unas 10¹⁰ operaciones, que es demasiado. Típicamente, un código es rápido si hace unas 10⁷ o 10⁸ (si son 10⁸, en general en los jueces online muchas veces ya da Time Limit) operaciones como mucho (siempre habrá que tener en cuenta el tipo de operaciones, no es lo mismo hacer raíces cuadradas que sumas).

Para este problema, una solución sencilla se puede hacer con coste nlogn. Si lees las palabras, las guardas en un vector y lo ordenas, es evidente que palabras iguales irán seguidas. Por lo tanto, bastará hacer una pasada al vector y contar cuántas seguidas iguales hay para cada palabra, puesto que ese número será el número de apariciones totales de la palabra por estar el vector ordenado.

No hay mucho misterio, si quieres programar bien y saber hacer ejercicios de programación, se aprende a base de programar. No es simple cuestión de conocer el lenguaje, sino de saber resolver problemas de tipo a veces más algorítmico que de implementación. Para todo esto, la única opción es practicar y para eso está el Jutge. A programar se aprende programando y si alguna cosa no te sale, pregunta.

Aparte de eso, intenta adaptarte al estilo que marcan en la asignatura para que no te bajen puntos por estilo (en la FIB con el grado no sé si lo siguen haciendo, pero me imagino que sí).

Por lo que veo estás haciendo un problema del Jutge en la versión catalana por el nombre de la función, así que asumiré que estás haciendo o un Grado en Matemáticas en la FME o un Grado en Informática en la FIB, que son las dos carreras que lo utilizan. Esto lo digo porque al ser la primera asignatura de programación, suelen ser estrictos con el estilo al programar, así que voy a intentar hacer todo según el estilo que marcan en ambas asignaturas.

Vayamos por partes. El último código que se ha puesto cuando lo envíes si lo envías verás que no funciona, puesto que hay un fallo que tenías que sigue ahí y es que haces casting a int con la variable k y el vector es de double, de manera que las comparaciones van a hacerse raras y el número si tenía decimales quedará modificado. Aparte de eso, en tu código utilizas un vector auxiliar que no se necesita para nada, de forma que gastas memoria tontamente haciendo el código además bastante más largo, cosa que en un examen te valorarían (o almenos deberían, con el grado no se cómo puntúan sobretodo en la FIB) bastante mal en la corrección manual, por mucho que el Jutge de un verde.

La idea de la solución es simple y es comenzar por el final e ir intercambiando los elementos mientras sea necesario.

Un pequeño código que he hecho y que debería funcionar es el siguiente:

#include <iostream>
#include <vector>
using namespace std;
 
void insereix(vector<double>& v){
    int n = v.size();
    for (int i = n - 1; i > 0 and v[i] < v[i - 1]; --i) swap(v[i], v[i - 1]);
}

Como ves, sin usar vectores auxiliares queda todo mucho más simple, natural y corto. La función swap no recuerdo si la podéis usar, si no podéis es muy sencilla de implementar (de hecho es uno de los problemas de la lista si no recuerdo mal).

Te menciono los que utilizo yo:

Olimpiada Informática Española (OIE): Página web de la Olimpiada Informática Española. Cada cierto tiempo se hacen concursos online para que los participantes de la olimpiada participen y entrenen. Además, cada año se realizan un par de concursos online para determinar a los seleccionados para la fase presencial (este próximo 2012 los clasificatorios son en abril y mayo), en la que se seleccionan a los 4 representantes españoles para la Olimpiada Informática Internacional. Para participar en los clasificatorios hay que ser elegible para España (en la web detalla las condiciones), pero en los demás concursos puede participar cualquiera. Además, en la sección de problemas se cuelgan todos los problemas que han aparecido en concursos anteriores, para poder resolverlos (con un juez online que valida la respuesta al momento) cuando uno quiera. Está íntegramente en castellano.

Jutge.org: Juez online creado por profesores de la Universidad Politècnica de Catalunya (UPC). Es de libre uso y contiene muchísimos problemas agrupados por categorías. Hay tanto problemas destinados para quien está empezando a programar (es el curso que se utiliza en la primera asignatura de programación en las carreras de Informática y Matemáticas), problemas para aprender algoritmia y estructuras de datos algo más avanzadas (es el curso utilizado en estas dos mismas carreras en la asignatura de algoritmia) y otros cursos como por ejemplo el que agrupa los problemas que han aparecido en los anteriores concursos de programación de la UPC (la dificultad, especialmente en los años recientes, es mucho más elevada que en el resto de problemas, dado que son los que se utilizan para elegir a los nueve representantes de la universidad en el SWERC). Todos los problemas están en inglés y a veces un segundo idioma (el original del problema si no es el inglés), que suele ser catalán, aunque en algunos es el castellano.

UVa: Juez de la universidad de Valladolid. Es sin duda el juez más famoso a nivel internacional, con miles de problemas de todos los niveles (aunque no están agrupados por dificultad ni por temática). Se realizan periódicamente concursos online también. Está íntegramente en inglés.

Timus: El mayor juez online ruso que existe. También tiene muchos problemas como la UVa, sin agrupar por temática o dificultad (son en general problemas extraídos de concursos online y por tanto aparecen en el orden en que se celebraron los concursos). La dificultad en general es más elevada que la de la UVa. También realiza periódicamente concursos online. Está en ruso e inglés.

SGU: Juez de Saratov. Es probablemente el segundo juez ruso más importante. Igual que Timus en cuanto a sus características y también se realizan concursos online. Sin embargo, los problemas suelen ser más difíciles en términos generales que en el Timus. Está en inglés y diría que también en ruso.

También hay jueces chinos que no menciono porque no suelo utilizar. Además, existen dos páginas que celebran periódicamente concursos online y que asigna un rating (una especie de ELO) a los participantes: Topcoder y Codeforces. La primera particularmente no me gusta, aunque es la más famosa. La segunda es rusa y me gusta mucho, participo habitualmente.

Además de todo esto, existen páginas u organizaciones que celebran concursos anualmente, como por ejemplo el famoso concurso de programación de Google: Google Code Jam.

Si quieres algo más de información, pregunta y te digo.

Te dejo mi solución que pasa los juegos de prueba en USACO:

import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class ride implements Runnable {
    PrintWriter writer;
    BufferedReader reader;
    StringTokenizer tokenizer;
 
    private void solve() throws IOException {
        String s = nextToken(), r = nextToken();
        int a = 1, b = 1;
        for (int i = 0; i < s.length(); ++i) a = (a*(Character.getNumericValue(s.charAt(i)) - 9))%47;
        for (int i = 0; i < r.length(); ++i) b = (b*(Character.getNumericValue(r.charAt(i)) - 9))%47;
 
        if (a == b) writer.println("GO");
        else writer.println("STAY");
    }
 
    public static void main(String[] args) {
        new ride().run();
    }
 
    public void run() {
        try {
            reader = new BufferedReader(new FileReader("ride.in"));
            writer = new PrintWriter(new FileWriter("ride.out"));
            tokenizer = null;
            solve();
            reader.close();
            writer.close();
        }
        catch (IOException e) {
        }
    }
 
    String nextToken() throws IOException {
        if (tokenizer == null || !tokenizer.hasMoreTokens())
            tokenizer = new StringTokenizer(reader.readLine());
        return tokenizer.nextToken();
    }
}

Pero eso no es búsqueda binaria, puesto que necesariamente tendrás que explorar en caso peor las dos mitades y tendrá complejidad lineal.

Una posible implementación de lo que te piden de forma algo cutre sería la siguiente:

#include <iostream>
#include <vector>
using namespace std;
 
int busca(int x, vector<int>& v, int a, int b) {
    if (a == b) return (v[a] == x) ? a : -1;
    return max(busca(x, v, a, (a + b)/2), busca(x, v, (a + b)/2 + 1, b));
}
 
int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    int x;
    while (cin >> x) cout << busca(x, v, 0, n - 1) << endl;
}

Y son dos líneas de código la función. Sin embargo, se podría optimizar la función, para que por ejemplo si la primera llamada recursiva encuentra el elemento, no haga la segunda llamada.

Como ya dije antes, si el array está desordenado, NO se puede hacer una búsqueda binaria, puesto que sería incorrecta. Si tienes que hacer una binaria por algún motivo, lo tendrás que ordenar antes.

Así que por mucho que lo intentes, el código es imposible que funcione sobre un vector desordenado.

La búsqueda binaria la puedes aplicar cuando tienes una función de entrada (en tu caso un array) que es monótona. Si el array no está ordenado, una búsqueda binaria no es correcta por motivos evidentes si entiendes como funciona con un array ordenado. Si quieres buscar un elemento en concreto necesitarás hacer una búsqueda lineal.

Simplemente como comentario, puesto que mucha gente no lo sabe, existe en C++ la librería complex, que permite trabajar con complejos directamente. Pongo un pequeño código que resuelve el problema usándola.

#include <iostream>
#include <complex>
using namespace std;
 
const double EPS = 1e-7;
 
int main() {
    complex<double> a, b, c;
    cin >> a >> b >> c;
    complex<double> x1 = (-b + sqrt(b*b - 4.0*a*c))/(2.0*a), x2 = (-b - sqrt(b*b - 4.0*a*c))/(2.0*a);
    cout << real(x1);
    if (fabs(imag(x1)) > EPS) cout << ((imag(x1) < 0)?"":"+") << imag(x1) << "i" << endl;
    else cout << endl;
    cout << real(x2);
    if (fabs(imag(x2)) > EPS) cout << ((imag(x2) < 0)?"":"+") << imag(x2) << "i" << endl;
    else cout << endl;
}