Number Game

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 30 Accepted Submission(s) : 10

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

有上下两个圆圈，每个圆圈边沿上均匀分布有N个点。上圆和下圆的点用一条竖直的直线连起来。将连续的自然数1到N，这N个数按逆时针方向放到下圆那N个不同的点上。将连续的自然数N+1到2*N，这N个数按逆时针方向放到上圆N个不同的点上。数字1上方的点对应上圆数字为N+1，2上方的数字为 N+2，...。右边点：为逆时针方向经过当前点到达的下一个点。同理，左边点为顺时针方向经过当前点到达的下一个点。有三种操作：A x y（保证x,y在同一竖线上)，表示将同一竖线上的两个数x,y对调位置；B x y（保证x,y在同一个圆上），表示将圆上的两个数x,y对调位置。Q x，则问你数字为x的这个点的左边那个点、右边那个点、上边或下边那个点上的数字分别是多少？

Input

第一行有一个整数n(0<n<10),表示有n组测试数据，随后每一组测试数据第一行是两个整数2N,M，其中2N表示两个圆上点的总个数 (5<2N<10000)，M表示操作的的次数(0<M<1000)。随后的M行，每行有三个变量 s x y，或两个变量s x。s表示操作的类型为A、B、Q;x，y为点上的数字。当s为Q时，若x为上圆的点则询问x的左边、右边、下边的点的数字；若x为下圆的点则询问x的左边、右边、上边的点的数字。

Output

输出每次询问的三个点的数字，输出顺序为左边、右边、下边，或左边、右边、上边，数字之间两两有一空格，每次询问完后输出一换行。

Sample Input

Sample Output

4 6 11

Author

jxust_acm

Source

xiexianwen

//这题关键的下标和数的对应关系

//hash数组，下标代表数，值代表下标

//rc数组，下标代表下标，值代表值、或许有些抽象吧、呵呵

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 10001
using namespace std;
int hash[N];
int rc[N];
int main()
{
    int T;
    int n,m;
    int i,j;
    char op;
    int l,r;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%d%d",&n,&m);
       for(i=1;i<=n;i++)
          hash[i]=i,rc[i]=i;
       while(m--)
       {
           getchar();
           scanf("%c",&op);
           if(op=='A') //写好后发现A和B的操作完全一样，可以放一起
           {
               scanf("%d%d",&i,&j);
              swap(rc[hash[i]],rc[hash[j]]);
              swap(hash[i],hash[j]);
           }
           else if(op=='B')
           {
               scanf("%d%d",&i,&j);
              swap(rc[hash[i]],rc[hash[j]]);
              swap(hash[i],hash[j]);
           }
           else
           {
               scanf("%d",&i);
               j=hash[i];
               if(j>n/2)
               {
                   l=j-1;if(l==n/2) l=n;
                   r=j+1;if(r>n) r=n/2+1;
                   j=j-n/2;
                   printf("%d %d %d\n",rc[l],rc[r],rc[j]);
               }
               else
               {
                   l=j-1;if(l==0) l=n/2;
                   r=j+1;if(r>n/2) r=1;
                   j=j+n/2;
                   printf("%d %d %d\n",rc[l],rc[r],rc[j]);
               }

           }
       }
    }
}
//小修改下

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 10001
using namespace std;
int hash[N];
int rc[N];
int main()
{
    int T;
    int n,m;
    int i,j,l,r;
    char op;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%d%d",&n,&m);
       for(i=1;i<=n;i++)
          hash[i]=i,rc[i]=i;
       while(m--)
       {
           getchar();
           scanf("%c",&op);
           if(op=='A'||op=='B')
           {
              scanf("%d%d",&i,&j);
              swap(rc[hash[i]],rc[hash[j]]);
              swap(hash[i],hash[j]);
           }
           else
           {
               scanf("%d",&i);
               j=hash[i];
               if(j>n/2)
               {
                   l=j-1;if(l==n/2) l=n;
                   r=j+1;if(r>n) r=n/2+1;
                   j=j-n/2;
                   printf("%d %d %d\n",rc[l],rc[r],rc[j]);
               }
               else
               {
                   l=j-1;if(l==0) l=n/2;
                   r=j+1;if(r>n/2) r=1;
                   j=j+n/2;
                   printf("%d %d %d\n",rc[l],rc[r],rc[j]);
               }
           }
       }
    }
}