Cod sursa(job #2926228)

Utilizator ezluciPirtac Eduard ezluci Data 17 octombrie 2022 12:13:59
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("date.in");
ofstream fout ("date.out");

const int nMAX = 30e3;

int n;
int aib[nMAX + 1]; // aib[i] = cate elemente nu sunt sterse in intervalul [i - (i&-i) + 1, i]


void buildAib()
{
   for (int i = 1; i <= n; ++i)
   {
      aib[i] += 1;
      if (i + (i&-i) <= n)
         aib[i + (i&-i)] += aib[i];
   }
}

void addAib(int pos, int val)
{
   for (; pos <= n; pos += pos & -pos)
      aib[pos] += val;
}

int queryAib(int dr)
{
   int sum = 0;
   for (; dr >= 1; dr -= dr & -dr)
      sum += aib[dr];

   return sum;
}

int bsAib(int val) // returneaza pozitia pos minima pentru care queryAib(pos) = val
{
   int pos = 0, sum = 0;
   for (int i = 31-__builtin_clz(n); i >= 0; --i)
   {
      if ((pos | (1<<i)) < n && sum + aib[pos | (1<<i)] < val)
      {
         pos |= 1<<i;
         sum += aib[pos];
      }
   }

   return pos+1;
}


int main()
{
   fin >> n;
   buildAib();

   int pos = 1;
   for (int i = 1; i <= n; ++i)
   {
      int inou = i % (n-i+1);
      int ramase = queryAib(pos); // cate elemente au ramas in intervalul [1, pos]

      if (ramase + inou <= n-i+1)
         pos = bsAib(max(1, ramase + inou));
      else // ramase + inou > n-i+1
         pos = bsAib(max(1, ramase + inou - (n-i+1)));

      addAib(pos, -1);
      fout << pos << ' ';
   }
}