[POJ] 1068 Parencodings.cpp

#include <cstdio>
using namespace std;
int main()
{
    int t,n,p_seq[25],parenthes[10000],n_p=0,i,j;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(p_seq[0]=0,i=1,n_p=0;i<=n;i++){
            scanf("%d",&p_seq[i]);
            for(j=0;j<p_seq[i]-p_seq[i-1];j++)
                parenthes[n_p++]=0;
            parenthes[n_p++]=1;
        }
        bool matched[10000]={0}; //1:left parenthes is matched
        for(i=0;i<n_p;i++){
            int num=0;
            if(parenthes[i]==1){
                for(j=1;i-j>=0;j++){
                    if(parenthes[i-j]==0 && matched[i-j]==0){
                        num++;
                        matched[i-j]=1;
                        printf("%d ",num);
                      break;
                    }
                    else if(parenthes[i-j]==0 && matched[i-j]==1)
                        num++;
                }
            }
        }
        printf("\n");
    }
    return 0;
}