Cod sursa(job #2297560)

Utilizator btudorBazac Tudor btudor Data 5 decembrie 2018 23:59:58
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>

using namespace std;

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

int n,aib[30100];

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

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

int caut(int x)
{
    int st=0,dr=n,q,mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        q=query(mid);
        if(x<=q)
            dr=mid;
        else
            st=mid+1;
    }
    return st;
}

int main()
{
    int i,x=2,r;
    in>>n;
    for(i=1;i<=n;i++)
        update(i,1);
    for(i=1;i<=n;i++)
    {
        x=(x+i-2)%(n+1-i)+1;
        r=caut(x);
        update(r,-1);
        out<<r<<" ";
    }
    return 0;
}