Cod sursa(job #1253595)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 1 noiembrie 2014 15:21:12
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream is("order.in");
ofstream os("order.out");

int n, p, el, aux;
vector<int> aib;
vector<bool> ok;

void UPDATE(int poz);
void DELETE (int poz);
int BS(int poz, int k);
int SUM(int poz);

int main()
{
    is >> n;
    aib.resize(n + 1);
    ok.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
        UPDATE(i);
    p = 1;
    for ( int i = 1; i < n; ++i )
    {
        el = BS(p, i);
        aux = i;
        while ( el == n + 1 )
        {
            aux -= SUM(n) - SUM(p);
            p = 0;
            el = BS(0, aux);
        }
        os << el << "\n";
        DELETE(el);
        ok[el] = true;
        p = el - 1;
        while ( ok[p] && p )
            --p;
        if ( p == n )
            p = 0;
        /*for ( int i = 1; i <= n; ++i )
            os << aib[i] << " ";
        os << "\n";*/
    }
    for ( int i = 1; i <= n; ++i )
        if ( !ok[i] )
        {
            os << i << "\n";
            break;
        }
    is.close();
    os.close();
    return 0;
}

int BS(int poz, int k)
{
    int st, dr, md, sum, answ = n + 1;
    st = poz + 1;
    dr = n;
    do
    {
        md = ( st + dr ) / 2;
        sum = SUM(md) - SUM(poz);
        if ( sum > k || ( sum == k && ok[md] ) )
            dr = md - 1;
        else
            if ( sum == k )
            {
                answ = min(answ, md);
                dr = md - 1;
            }
            else
                st = md + 1;
    } while ( st <= dr );
    return answ;
}

void UPDATE(int poz)
{
    for ( ; poz <= n; poz += poz & -poz )
        ++aib[poz];
}

void DELETE(int poz)
{
    for ( ; poz <= n; poz += poz & -poz )
        --aib[poz];
}

int SUM(int poz)
{
    int s = 0;
    for ( ; poz; poz -= poz & -poz )
        s += aib[poz];
    return s;
}