Cod sursa(job #1776317)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 11 octombrie 2016 10:16:39
Problema Order Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia2-arborideintervale Marime 2.51 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2140000000
#define MaxVal 100000
#define MaxT 66000
#define MaxN 30001
#define MAX 65536
using namespace std;
  
FILE *IN,*OUT;
int N,pos=0,out=0,sign,Ans,R,v[MaxN],Size,Act=0;
char f[MAX],Out[MAX],str[10];
  
struct _Tree
{
    int Min,Lower,Pos;
}T[MaxT];
inline void Write_Ch(char ch)
{
    Out[out++]=ch;
    if(out==MAX)
        fwrite(Out,MAX,1,OUT),out=0;
}
inline void Write_Int(int nr)
{
    int x=0;
    if(nr<0)Write_Ch('-'),nr=-nr;
    do
    {
        str[x++]=nr%10+'0';
        nr/=10;
    }
    while(nr);
    while(x>0)
        Write_Ch(str[--x]);
}
inline int min2(int a,int b)
{
    if (a<b) return a;
    else return b;
}
inline void Read(int &nr)
{
    sign=0;
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        if(f[pos]=='-')sign=1;
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    if(sign)nr=-nr;
}
 
void DFS(int node,int start,int end)
{
    if(start==end)
        T[node].Pos=start,T[node].Min=v[start];
    else
    {
        int mid=(start+end)>>1;
        DFS(2*node,start,mid);
        DFS(2*node+1,mid+1,end);
        T[node].Min=T[2*node].Min,T[node].Pos=T[2*node].Pos;
    }
}
int Query(int Val,int node,int start,int end)
{
    int ret;
    if(start==end)
    {
        T[node].Min=INF;
        return T[node].Pos;
    }
    else
    {
        int mid=(start+end)/2;
        if(Val>=T[2*node+1].Min)
            ret=Query(Val+T[2*node+1].Lower,node*2+1,mid+1,end);
        else
        {
            T[2*node+1].Lower++;
            T[2*node+1].Min--;
            ret=Query(Val+T[2*node].Lower,node*2,start,mid);
        }
        T[node].Min=T[2*node].Min,T[node].Pos=T[2*node].Pos;
        if(T[2*node+1].Min<T[node].Min)T[node].Min=T[2*node+1].Min,T[node].Pos=T[2*node+1].Pos;
        T[node].Min-=T[node].Lower;
    }
    return ret;
}
int main()
{
    IN=fopen("order.in","r");
    OUT=fopen("order.out","w");
  
    fread(f,1,MAX,IN);
    Read(N);
    for(int i=1;i<=N;i++)
        v[i]=i-1;
    DFS(1,1,N);
    Size=N,Act=1;
    for(int i=1;i<=N;i++)
    {
        Act=(Act+i-1)%Size;
        Size--;
        Ans=Query(Act,1,1,N);
        Write_Int(Ans);
        Write_Ch(' ');
    }
    if(out>0)fwrite(Out,1,out,OUT);
    return 0;
}