Cod sursa(job #1014142)

Utilizator cahemanCasian Patrascanu caheman Data 22 octombrie 2013 10:14:44
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<cstdio>

using namespace std;

int aib[33000], put2;
int v[33000];

int min(int a, int b)
{
  if(a < b)
    return a;
  else
    return b;
}

void update(int x)
{
  int x2;
  x2 = x;
  while(x2 <= put2)
  {
    -- aib[x2];
    x2 += (x2 & - x2);
  }
}

int query(int poz)
{
  int sum = 0, cpoz;
  cpoz = poz;
  while(cpoz)
  {
    sum += aib[cpoz];
    cpoz -= (cpoz & - cpoz);
  }
  return sum;
}

int cb(int st, int dr, int val)
{
  int med, x, last;
  if(val == 0)
    val = aib[put2];
  while(st <= dr)
  {
    med = (st + dr) >> 1;
    x = query(med);
    if(x >= val)
    {
      last = med;
      dr = med - 1;
    }
    else
      st = med + 1;
  }
  return last;
}

int main()
{
  int n, i, poz, misc, j, t, x;
  scanf("%d", &t);
  for(j = 1; j <= t; ++ j)
  {
    scanf("%d", &n);
    for(i = 1; i <= n; ++ i)
      if(i % 2)
        aib[i] = 1;
      else
        aib[i] = aib[i >> 1] << 1;
    put2 = 1;
    while(put2 < n)
    {
      put2 = put2 << 1;
    }
    for(i = n + 1; i <= put2; ++ i)
    {
      if(i % 2)
        aib[i] = 1;
      else
        aib[i] = aib[i >> 1] << 1;
      aib[i] = min(n, aib[i]);
    }
    poz = 0;
    for(i = 2; i <= n; ++ i)
    {
      x = query(put2) - query(poz);
      if(x < i)
        poz = cb(1, n, (i - x) % aib[put2]);
      else
        poz = cb(1, n, i + query(poz));
      v[poz] = i - 1;
      update(poz);
    }
    for(i = 1; i <= n; ++ i)
      if(v[i])
        printf("%d ", v[i]);
      else
        printf("%d ", n);
    for(i = 1; i <= n; ++ i)
      v[i] = 0;
    printf("\n");
  }
  return 0;
}