whust 2016 #1 H - Pair: normal and paranormal

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月07日 星期日 17时34分13秒
  4File Name :code/whust2016/#1/HH.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10
 11#include <algorithm>
 12#include <vector>
 13#include <queue>
 14#include <stack>
 15#include <set>
 16#include <map>
 17#include <string>
 18#include <cmath>
 19#include <cstdlib>
 20#include <deque>
 21#include <ctime>
 22#include <cctype>
 23#define fst first
 24#define sec second
 25#define lson l,m,rt<<1
 26#define rson m+1,r,rt<<1|1
 27#define ms(a,x) memset(a,x,sizeof(a))
 28typedef long long LL;
 29#define pi pair < int ,int >
 30#define MP make_pair
 31
 32using namespace std;
 33const double eps = 1E-8;
 34const int dx4[4]={1,0,0,-1};
 35const int dy4[4]={0,-1,1,0};
 36const int inf = 0x3f3f3f3f;
 37const int N=1E4+7;
 38char st[N];
 39int s[N];
 40int n;
 41int plow[N];
 42int pup[N];
 43int ans[N];
 44stack<int>stk;
 45
 46
 47bool ok(int  x, int y)
 48{
 49  //  cout<<"x:"<<x<<" y:"<<y<<endl;
 50    if (plow[x]>0&&pup[y]>0)
 51    {
 52	ans[pup[y]] = plow[x];
 53	 return true;
 54    }
 55    if (plow[y]>0&&pup[x]>0)
 56    {
 57	ans[pup[x]] = plow[y];
 58	return true;
 59    }
 60    return false;
 61}
 62int main()
 63{
 64	#ifndef  ONLINE_JUDGE 
 65	freopen("code/in.txt","r",stdin);
 66  #endif
 67
 68	cin>>n>>st;
 69	n*=2;
 70	int cntA = 0 ;
 71	int cnta = 0 ;
 72	ms(pup,0);
 73	ms(plow,0);
 74	for ( int i = 0 ; i < n ; i++)
 75	{
 76	    if (st[i]>='a'&&st[i]<='z')
 77	    {
 78		cnta++;
 79		plow[i] = cnta;
 80	    }
 81	    else
 82	    {
 83		cntA++;
 84		pup[i] = cntA;
 85	    }
 86	}
 87//	for ( int i = 0 ; i < n ; i++) cout<<"plow[i]:"<<plow[i]<<" pup[i]:"<<pup[i]<<endl;
 88	for ( int i = 0 ; i < n ; i++)
 89	{
 90	    st[i] = toupper(st[i]);
 91	}
 92//	cout<<"st:"<<st<<endl;
 93	ms(ans,-1);
 94	while (!stk.empty()) stk.pop();
 95	stk.push(0);
 96	for ( int i =  1 ; i < n ; i++)
 97	{
 98	    while (!stk.empty()&&st[stk.top()]==st[i]&&ok(stk.top(),i)&&i<n) 
 99	    {
100		stk.pop();
101		i++;	
102	    }
103	    stk.push(i);    
104	}
105	for ( int i = 1 ; i <= n/2 ; i++) 
106	{
107	    if (ans[i]==-1)
108	    {
109		puts("Impossible");
110		return 0;
111	    }
112	}
113	for ( int i = 1 ; i < n/2 ; i++) printf("%d ",ans[i]);
114	printf("%d\n",ans[n/2]);
115
116  #ifndef ONLINE_JUDGE  
117  fclose(stdin);
118  #endif
119    return 0;
120}