Cod sursa(job #241117)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 9 ianuarie 2009 15:02:00
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
//aib
#include <fstream>
#include <iostream>
#define loop (poz^(poz-1))&poz

using namespace std;


int sir[1000001];
char poz[1000001];
int n,lg;
int *val;

int suma (int poz)
{
     int S=0;
     while (poz>0)
     {
          S+=sir[poz];
          poz-=loop;
     }
     return S;
}

void update(int poz,int val)
{
     while (poz<lg)
     {
          sir[poz]+=val;
          poz+=loop;
     }
}

int poz_min(int S)
{
     int putere,i;
     for (putere=1;putere<lg;putere<<=1);

     for (i=lg-1; putere!=0; putere>>=1)
     if (i-putere>=1)
     if (S<=suma(i-putere))
          i-=putere;
     return i;
}

void citire()
{
     val =new int [1000000];
     char sir[1000000],lol[1000000];
     cin.getline(lol,1000000);
     int n=strlen(lol);
     char c;
     int pozz=1;
     lg=1;
     for (int i=0;i<n;i++)
     {
          c=lol[i];
          if (c>='a'&&c<='z')
          {
               sir[lg]=c;
               val[lg]=pozz;
               lg++;
               pozz++;
          }
          else
               if (c=='L')
               {
                    if (pozz>1)
                         pozz--;
               }
               else
               {
                    if (pozz<=lg)
                         pozz++;
               }
     }

     for (int i=1;i<=1000000;i++)
          update(i,1);

     for (int i=lg-1;i>0;i--)
     {
          int aux=poz_min(*(val+i));
          poz[aux]=sir[i];
          update(aux,-1);
     }

     for (int j=1;j<=n;j++)
          cout<<poz[j];
}

int main ()
{
     citire();
     return 0;
}