Cod sursa(job #1828730)

Utilizator robx12lnLinca Robert robx12ln Data 13 decembrie 2016 20:10:16
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n, nr, poz, sol[30005], aib[30005];
void erase( int p ){
    for( ; p <= n; p += (p&(-p)) ){
        aib[p] += 1;
    }
    return ;
}
int query( int p ){
    int sum = 0;
    for( ; p > 0; p -= (p&(-p)) ){
        sum += aib[p];
    }
    return sum;
}
int get_number( int x ){
    int mid = 0;
    int st = 1;
    int dr = n;
    int number = (1<<30);
    while( st <= dr ){
        mid = ( st + dr ) / 2;
        int s = query( mid );
        if( mid - s == x ){
            number = min( number, mid );
            dr = mid - 1;
        }else{
            if( mid - s < x ){
                st = mid + 1;
            }else{
                dr = mid - 1;
            }
        }
    }
    return number;
}
int main(){
    fin >> n;
    poz = 2;
    nr = n;
    for( int i = 1; i <= n; i++ ){
        poz += i - 1;
        poz %= nr;
        if( poz == 0 ){
            poz = nr;
        }
        sol[i] = get_number( poz );
        erase( sol[i] );
        nr--;
    }
    for( int i = 1; i <= n; i++ ){
        fout << sol[i] << " ";
    }
    return 0;
}