注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

APIO2008[珠链交换器/beads]  

2010-04-21 14:01:14|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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;

}

 

  评论这张
 
阅读(492)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018