Cod sursa(job #1255257)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 4 noiembrie 2014 16:24:43
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <iostream>
#include <vector>
//#define os cout
using namespace std;

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

int n;
vector<int> a;
vector<bool> ok;

void UPDATE(int poz, int val);
int BS(int poz, int val);
int SUM(int poz);

int main()
{
    is >> n;
    a.resize(n + 1);
    ok.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
        UPDATE(i, 1);
    int start = 1, val, rez;
    for ( int i = 1; i < n; ++i )
    {
        if ( start == n )
            start = 0;
        rez = BS(start, i);
        if ( rez != -1 )
        {
            os << rez << " ";
            ok[rez] = true;
            UPDATE(rez, -1);
            start = rez - 1;
            continue;
        }
        //os << "\n\n" << i << "!"; cin.get();
        val = i - SUM(n) + SUM(start);
        start = 0;

        //os << val; cin.get();
        if ( val > n - i + 1  )
            val %= ( n - i + 1 );//, os << "!!!" << val << "!!!";
        //os << val; cin.get();
        //for ( int i = 1; i <= n; ++i )
            //os << a[i] << " " << SUM(i) << " ! ";
        //cin.get();
        rez = BS(start, val);
        //os << "!!";cin.get();
        os << rez << " ";
        //os << "rez "; cin.get();
        if ( rez > 0 )
        {ok[rez] = true;
        UPDATE(rez, -1);
        start = rez - 1;}
    }
    for ( int i = 1; i <= n; ++i )
        if ( !ok[i] )
            os << i, i = n;
    is.close();
    os.close();
    return 0;
}

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

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

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