Cod sursa(job #3323299)

Utilizator StonkDavid Andrei Mateis Stonk Data 17 noiembrie 2025 23:30:43
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <iostream>

using namespace std;

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

int N;
int sumT;

int eliminati[60000];

int lsb(int x) {
  return x & (-x);
}

void debug_aib() {
  for(int i = 1; i <= 32; i++)
    cout << i << ": " << eliminati[i] << '\n';
}

void bump(int pos, int val) {
  for(int i = pos; i <= 1 << 15; i += lsb(i))
    eliminati[i] += val;
}

int sum(int pos) {
  int sum = 0;
  for(int i = pos; i >= 1; i -= lsb(i)){
    sum += eliminati[i];
  }
  return sum;
}

int shiftf(int spos, int locuri) {
  int sumi = sum(spos);
  int pos = 0;
  int sum = 0;
  do {
  pos = 0;
  for (int pas = 1 << 15; pas >= 1; pas /= 2){
    //cout << pas << " sum: " << sum << " to add: " << eliminati[pos + pas] << '\n';
    if(sum + eliminati[pos + pas] - sumi < locuri &&
      pos + pas <= N) {
      sum += eliminati[pos + pas];
      pos += pas;
      //cout << "stepped " << pas << '\n';

    }
  }
  } while (pos >= N);
  return pos + 1;
}

int main(){ 
  fin >> N;

  for(int i = 1; i <= N; i++){
    eliminati[i] += lsb(i);
  }
  //debug_aib();
  
  int pos = 1;
  sumT = N;
  
  for(int i = 1; i <= N; i++){
    pos = shiftf(pos, i);
    bump(pos, -1);
    sumT--;
    fout << pos << ' ';
  }
  
  return 0;
  
}