Cod sursa(job #3261060)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 4 decembrie 2024 11:37:13
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>

#define MAXN 30001

struct fenwick{
private:
  int aib[MAXN];
  int n;
  void update(int idx, int val){
    while(idx<=n){
      aib[idx] += val;
      idx+=(idx&-idx);
    }
  }
public:
  void init(int n){
    this->n = n;
  }
  void add(int idx){
    update(idx, 1);
  }
  void del(int idx){
    update(idx, -1);
  }
  int query(int idx){
    int sum = 0;
    while(idx>0){
      sum+=aib[idx];
      idx -= (idx&-idx);
    }
    return sum;
  }
};

int n;
fenwick aib;

int main(){
  FILE *fin, *fout;
  fin = fopen("order.in", "r");
  fscanf(fin, "%d", &n);
  fclose(fin);

  aib.init(n);
  for(int i=1; i<=n; i++){
    aib.add(i);
  }

  fout = fopen("order.out", "w");
  int pos = 2;
  int remain = n;
  int i = 0;
  while(remain>0){
    pos = (pos+i)%remain;
    if(!pos) pos = remain;
    remain--;
    int s = 0;
    int d = n;
    while(d-s>1){
      int m = (s+d)/2;
      if(aib.query(m)<pos) s = m;
      else d = m;
    }
    aib.del(d);
    fprintf(fout, "%d ", d);
    i++;
  }
  fclose(fout);
  return 0;
}