Cod sursa(job #3245250)

Utilizator angelaAngela Visuian angela Data 28 septembrie 2024 07:36:24
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;
	
ifstream fin("order.in");
ofstream fout("order.out");
	
int  N;   
int  n;   
int lg;   

int aib[30003];  
	
void Update(int p, int v)  
{
    for(int i = p; i <= N; i += i & -i) 
		aib[i] += v;
}
		
int Query(int p) 
{	
    int s = 0;
	
    for (int i = p; i >= 1; i -= i & -i) 
		s += aib[i];
	
    return s;
}
	

int BSearch(int lg) 
{
    int st = 1, dr = N, m = 0, nr = 0, p_min = 0;
	
    while (st <= dr) 
    {
        m = (st + dr) / 2;
        nr = Query(m);    
	
		if (nr >= lg)
		{
			p_min = m;
			dr = m - 1;
		}		
		else
			st = m + 1;
    }
	
    return p_min;
}


int main() 
{	
    fin >> N;
	
    for (int i = 1; i <= N; i++) 
		Update(i, 1);
	
    n = N, lg = 2;
	
    for (int i = 1; i <= N; i++) 
    {
        int p = BSearch(lg);  
        Update(p, -1);        
	
        fout << p << ' ';
        n--;    
	
        lg += i;
        if (n) 
			lg = lg % n == 0 ? n : lg % n;
		
    }
	
	
    return 0;
}