Cod sursa(job #1435986)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 14 mai 2015 21:05:21
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#define int64 long long
#define lsb(x) (-x)&(x)
#define INF numeric_limits<int>::max()
#define mp make_pair
#define pb push_back
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
vector<int> aib;
int n;
void mark(int pos,int val)
{
    for(int i=pos;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int qsum(int pos)
{
    int s=0;
    for(int i=pos;i>0;i-=lsb(i))
        s+=aib[i];
    return s;
}
int getpos(int x)
{
    int left=1,right=n;
    while(left<=right)
    {
        int mid=(left+right)/2;
        int sum=qsum(mid);
        if(sum==x)return mid;
        else if(sum>x)right=mid-1;
        else left=mid+1;
    }
    return -1;
}
int main()
{
    in>>n;
    aib=vector<int> (n+1);
    for(int i=1;i<=n;i++)mark(i,1);
    for(int pos=1,step=1;step<=n;step++)
    {
        int s=qsum(n)-qsum(pos),st=step;
        if(st>s)
        {
            while(st>s)
            {
                st-=s;
                s=qsum(n);
            }
            pos=getpos(st);
        }
        else pos=getpos(st+qsum(pos));
        mark(pos,-1);
        out<<pos<<' ';
    }
    return 0;
}