uva 120 Stacks of Flapjacks

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=105;
7int n;
8int a[N];
9string in;

 1struct node
 2{
 3    int value;
 4    int id;
 5}q[N];
 6int pos[N];
 7bool cmp1(node a,node b)
 8{
 9    return a.value<b.value;
10}
11bool cmp2(node a,node b)
12{
13    return a.id<b.id;
14}

1void flip2( int x)
2{
3    for ( int i = 1 ; i <= x/2 ; i++)
4    {
5	swap(q[i].value,q[x+1-i].value);
6    }
7}

1void print( int n)
2{
3    for ( int i = 1 ; i <= n ; i ++) printf(" %d ",q[i].value);
4    printf("\n");
5}

 1void getpos( int n)
 2{
 3    for ( int i = 1 ; i <=  n ; i++)
 4    {
 5	pos[q[i].value] = i;
 6    }
 7}
 8int main()
 9{
10	#ifndef  ONLINE_JUDGE 
11	freopen("code/in.txt","r",stdin);
12  #endif

1	while (getline(cin,in))
2	{
3	    ms(pos,-1); //pos[i]表示数字i的位置
4	   // cout<<"oriin:"<<in<<endl;
5	    int p = in.find(' ');
6	    int val;
7	    int cnt = 0 ; 
8	    while (p!=-1)
9	    {

 1		string tmp = in.substr(0,p);
 2		sscanf(tmp.c_str(),"%d",&val);
 3		in.erase(0,p+1);
 4		p = in.find(' ');
 5	//	cout<<"in:"<<in<<endl;
 6		cnt++;
 7		a[cnt] = val;
 8	    }
 9	    sscanf(in.c_str(),"%d",&val);
10	    cnt++;
11	    a[cnt]=val;

1	   for ( int i = 1 ; i <= cnt ; i++) cout<<a[i]<<" ";
2	   cout<<endl;
3	  //hash
4	    for ( int i = 1 ; i <= cnt ; i++)
5	    {
6		q[i].value = a[i];
7		q[i].id = i ;
8	    }

1	    sort(q+1,q+cnt+1,cmp1);
2	    int hashnum = 0;
3	    for ( int i = 1 ; i <=cnt ; i++)
4	    {
5		hashnum++;
6		q[i].value = hashnum;
7	    }
8	    sort(q+1,q+cnt+1,cmp2);

1	    for ( int i = 1 ; i <= cnt ; i++)
2	    {
3		pos[q[i].value] = i ;
4	    }

 1	   // print(cnt);
 2	    for ( int i = cnt ; i >=1 ; i--)
 3	    {
 4		if (pos[i]==i) continue;
 5		if (pos[i]==1)
 6		{
 7		    printf("%d ",cnt+1-i);
 8		    flip2(i);
 9		 //   print(cnt);
10		    getpos(cnt);

 1		}
 2		else
 3		{
 4		    printf("%d ",cnt+1-pos[i]);
 5		    flip2(pos[i]);
 6		  //  print(cnt);
 7		    getpos(cnt);
 8		    printf("%d ",cnt+1-i);
 9		    flip2(i);
10		  //  print(cnt);
11		    getpos(cnt);
12		}
13	    }   
14	    puts("0");

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}