whust 2016 #1 H - Pair: normal and paranormal

1#include <cstdio>
2#include <cstring>
3#include <iostream>

 1#include <algorithm>
 2#include <vector>
 3#include <queue>
 4#include <stack>
 5#include <set>
 6#include <map>
 7#include <string>
 8#include <cmath>
 9#include <cstdlib>
10#include <deque>
11#include <ctime>
12#include <cctype>
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=1E4+7;
 7char st[N];
 8int s[N];
 9int n;
10int plow[N];
11int pup[N];
12int ans[N];
13stack<int>stk;

 1bool ok(int  x, int y)
 2{
 3  //  cout<<"x:"<<x<<" y:"<<y<<endl;
 4    if (plow[x]>0&&pup[y]>0)
 5    {
 6	ans[pup[y]] = plow[x];
 7	 return true;
 8    }
 9    if (plow[y]>0&&pup[x]>0)
10    {
11	ans[pup[x]] = plow[y];
12	return true;
13    }
14    return false;
15}
16int main()
17{
18	#ifndef  ONLINE_JUDGE 
19	freopen("code/in.txt","r",stdin);
20  #endif

 1	cin>>n>>st;
 2	n*=2;
 3	int cntA = 0 ;
 4	int cnta = 0 ;
 5	ms(pup,0);
 6	ms(plow,0);
 7	for ( int i = 0 ; i < n ; i++)
 8	{
 9	    if (st[i]>='a'&&st[i]<='z')
10	    {
11		cnta++;
12		plow[i] = cnta;
13	    }
14	    else
15	    {
16		cntA++;
17		pup[i] = cntA;
18	    }
19	}
20//	for ( int i = 0 ; i < n ; i++) cout<<"plow[i]:"<<plow[i]<<" pup[i]:"<<pup[i]<<endl;
21	for ( int i = 0 ; i < n ; i++)
22	{
23	    st[i] = toupper(st[i]);
24	}
25//	cout<<"st:"<<st<<endl;
26	ms(ans,-1);
27	while (!stk.empty()) stk.pop();
28	stk.push(0);
29	for ( int i =  1 ; i < n ; i++)
30	{
31	    while (!stk.empty()&&st[stk.top()]==st[i]&&ok(stk.top(),i)&&i<n) 
32	    {
33		stk.pop();
34		i++;	
35	    }
36	    stk.push(i);    
37	}
38	for ( int i = 1 ; i <= n/2 ; i++) 
39	{
40	    if (ans[i]==-1)
41	    {
42		puts("Impossible");
43		return 0;
44	    }
45	}
46	for ( int i = 1 ; i < n/2 ; i++) printf("%d ",ans[i]);
47	printf("%d\n",ans[n/2]);

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