Cod sursa(job #3177781)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 29 noiembrie 2023 23:42:02
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,no_of_one,pos,x;
vector<int>aib;
void update(int node,int value)
{
    for(; node<=n; node+=node&(-node))
        aib[node]+=value;
}
int query(int node)
{
    int ans=0;
    for(; node>0; node-=node&(-node))
        ans+=aib[node];
    return ans;
}
int magical_binary_search(int value)
{
    int ans=0,curr_sum=0;
    for(int step=(1<<30); step>0; step>>=1) ///we search for the last position with the sum strictly smaller than value
        if(ans+step<=n && curr_sum+aib[ans+step]<value)
        {
            ans+=step;
            curr_sum+=aib[ans];
        }
    if(ans+1>n || query(ans+1)!=value) ///if the sum for the next position isn't equal to value we return -1
        return -1; ///not gonna happen in this problem
    return ans+1;
}
int main()
{
    f>>n;
    aib.resize(n+1);
    ///later we want to find the ith 1,
    ///so its easier to start with all elements being 1
    for(int i=1; i<=n; i++)
        update(i,1);
    no_of_one=1;
    for(int i=1; i<=n; i++)
    {
        x=(no_of_one+i)%(n-i+1);
        if(x==0)
            x=n-i+1;
        pos=magical_binary_search(x); /// we search for the (position of current one + i)th one in a circular array,
        /// hence, we take (position of current one + i)%(n-i+1) to find it in our normal array
        update(pos,-1); /// we update that position with -1 because it can't be used anymore
        no_of_one=query(pos); /// we find the number of ones up until pos
        g<<pos<<' ';
    }
    return 0;
}