APIO2008[珠链交换器/beads]

就是记录一下每个球的路径。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-21

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

 

//LIB

int getNumQuestions()

{

    int Q;

    scanf(“%d\n”,&Q);

    return Q;

}

void getQuestion(int& K, int& J)

{

     scanf(“%d %d\n”,&K,&J);

}

void answer(int x)

{

     printf(“%d\n”,x);

}

//END LIB

 

struct Record{int ball,pos,where;};

 

#define MAXN 300000

#define MAXM 300000

 

int N,M;

int exchange[MAXM];

int ball[MAXN];

int counter;

Record data[MAXM*2+MAXN];

int begin[MAXN];

int end[MAXN];

 

int compare(const void* a,const void* b)

{

    if (((Record*)a)->ball<((Record*)b)->ball)

       return –1;

    else if (((Record*)a)->ball>((Record*)b)->ball)

         return 1;

    else  if ((((Record*)a)->pos)<(((Record*)b)->pos))

          return –1;

    else return 1;

}

void swap(int& a,int& b)

{

     int s=a;

     a=b;

     b=s;

}

int getAnswer(int K,int J)

{

    int l=begin[K],r=end[K];

    while (l+1!=r)

    {

          int mid=(l+r)>>1;

          if (data[mid].pos<=J) l=mid;

          else r=mid;

    }

    return data[l].where;

}

void prepare()

{

     for (int i=0;i<N;i++)

         ball[i]=i;

    

     for (int i=0;i<N;i++)

     {

         data[counter].ball=i;

         data[counter].pos=0;

         data[counter].where=i;

         counter++;

     }

     for (int i=0;i<M;i++)

     {

         data[counter].ball=ball[exchange[i]-1];

         data[counter].pos=i+1;

         data[counter].where=exchange[i];

         counter++;

         data[counter].ball=ball[exchange[i]];

         data[counter].pos=i+1;

         data[counter].where=exchange[i]-1;

         counter++;

         swap(ball[exchange[i]-1],ball[exchange[i]]);

     }

    

     qsort(data,counter,sizeof(Record),compare);

    

     int pointer=0;

     for (int i=0;i<N;i++)

     {

         begin[i]=pointer;

         while (data[pointer].ball==i) pointer++;

         end[i]=pointer;

     }

}

 

int main()

{

    //freopen(“beads.in”,”r”,stdin);

    //freopen(“beads.out”,”w”,stdout);

   

    scanf(“%d %d\n”,&N,&M);

    for (int i=0;i<M;i++)

        scanf(“%d\n”,&exchange[i]);

   

    prepare();

   

    int Q=getNumQuestions();

    for (int i=0;i<Q;i++)

    {

        int K,J;

        getQuestion(K,J);

        answer(getAnswer(K-1,J)+1);

    }

   

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}