Cod sursa(job #1419808)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 16 aprilie 2015 16:45:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#define bit(x) (x&(-x))
#define DIM 30002

using namespace std;

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

int N, queue ,remaining_kids;
int aib[DIM];

void update(int poz,int val){
    for(int i=poz;i<=N;i+=bit(i))
        aib[i]+=val;
}
int query(int poz){
    int sum=0;
    for(int i=poz;i>=1;i-=bit(i))
        sum+=aib[i];
    return sum;
}
int main(){
    fin>>N;
    remaining_kids=N;
    queue=2;
    for(int i=1;i<=N;i++)
        aib[i]=bit(i);
    for(int i=1;i<=N;i++){
        int p=1;
        int u=N;
        int poz=0x3f3f3f3f;
        remaining_kids--;
        while(p<=u){
            int mid=(p+u)>>1;
            int x=query(mid);
            if(x==queue && poz>mid){
                poz=mid;
                u=mid-1;
                continue;
            }
            if(x>queue)
                u=mid-1;
            else
                p=mid+1;
        }
        fout<<poz<<" ";
        update(poz,-1);
        queue+=i;
        if(remaining_kids)
            queue%=remaining_kids;
        if(!queue)
            queue=remaining_kids;
    }
    fin.close();fout.close();
    return 0;
}