1586 - Cabo de Guerra

#include <iostream>

using namespace std;

int i, j;
int n;
string nome[100010];
long long int forca[100010];

int binaria()
{
    bool achou = false;
    int baixo = 0;
    int alto = n - 1;
    int meio;
    long long int fa, fb;
    int pos;

    while(baixo <= alto && achou == false)
    {
        meio = (baixo + alto) / 2;

        fa = 0;
        for(i = 0; i <= meio; i++)
            fa += forca[i] * (meio - i + 1);
        fb = 0;
        for(i = meio + 1; i < n; i++)
            fb += forca[i] * (i - meio);

        if(fa == fb)
        {
            pos = meio;
            achou = true;
        }
        if(fa > fb)
            alto = meio - 1;
        if(fa < fb)
            baixo = meio + 1;
    }

    if(achou)
        return pos;
    else
        return -1;
}

int main ()
{
    int pos;

    cin >> n;
    while(n != 0)
    {
        for(i = 0; i < n; i++)
        {
            cin >> nome[i];

            forca[i] = 0;
            for(j = 0; j < (int)nome[i].size(); j++)
                forca[i] += (int)nome[i][j];
        }

        pos = binaria();

        if(pos != -1)
            cout << nome[pos] << '\n';
        else
            cout << "Impossibilidade de empate." << '\n';

        cin >> n;
    }

    return 0;
}