Cod sursa(job #1510612)

Utilizator vladrochianVlad Rochian vladrochian Data 25 octombrie 2015 13:09:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
using namespace std;

const int kMaxN = 30005;

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

int N;
int aib[kMaxN];

void Erase(int pos) {
   for (int i = pos; i <= N; i += i & -i)
      --aib[i];
}

int Search(int sum) {
   int pos = 0;
   for (int step = 1 << 14; step; step >>= 1)
      if ((pos ^ step) <= N && aib[pos ^ step] < sum) {
         pos ^= step;
         sum -= aib[pos];
      }
   return pos + 1;
}

int main() {
   fin >> N;
   for (int i = 1; i <= N; ++i)
      aib[i] = i & -i;

   for (int i = 0, pos = 2; i < N; ++i) {
      pos = (pos + i) % (N - i);
      if (pos == 0)
         pos = N - i;
      int indx = Search(pos);
      fout << indx << " ";
      Erase(indx);
   }
   fout << "\n";
   return 0;
}