Cod sursa(job #2925598)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 15 octombrie 2022 19:40:10
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n,aib[30005];
void update(int poz,int val)
{
    int i;
    for(i=poz; i<=n; i+=i&(-i))
    {
        aib[i]+=val;
    }
}
int query(int x)
{
    int i;
    int s=0;

    for(i=x; i>0; i-=i&(-i))
    {
        s+=aib[i];
    }
    return s;
}
int bs(int x)
{
    int s=0;

    int st=1;
    int dr=n;
    int poz=0;
    while(st<=dr)
    {
        int  mij=(st+dr)/2;
        int s=query(mij);
        if(s<x)
        {
            st=mij+1;
        }
        else if(x<s)
        {
            dr=mij-1;
        }
        else
        {
            poz=mij;
            dr=mij-1;

        }
    }
    return poz;
}
int main()
{
    fin>>n;
    int i;

    for(i=1; i<=n; i++)
    {
        update(i,1);
    }
    int sol,poz=2;
    for(i=1; i<=n; i++)
    {
        poz=(poz+i-1)%(n-i+1);
        if(!poz)
            poz=n-i+1;
        sol=bs(poz);
              while(query(sol) == poz)
            sol--;
        sol++;
        fout<<sol<<" ";
        update(sol,-1);

    }
    return 0;
}