题意翻译

现在有一个长度为的括号序列，其中，左括号和右括号数量都为。

对于从左到右的第个左括号，与其配对的右括号和这个左括号之间的距离需要在 之间。

请找出一种合法的匹配方案，使其可以满足所有左括号的要求。

若存在多种方案，则只输出其中一种即可。

输入格式

输入文件共有行，第一行给出，表示左括号的数量

之后的行，每行包含两个整数。表示该左括号的距离要求。

输出格式

输出仅有一行，如果满足限制的括号序列存在，则输出任意一个。

否则请输出IMPOSSIBLE。

Input & Output 's examples

Input 's eg 1

4
1 1
1 1
1 1
1 1

Output 's eg 1

()()()()

Input 's eg 2

3
5 5
3 3
1 1

Output 's eg 2

((()))

Input 's eg 3

3
5 5
3 3
2 2

Output 's eg 3

IMPOSSIBLE

Input 's eg 4

3
2 3
1 4
1 4

Output 's eg 4

(())()

数据范围和约定

对于的数据，保证,。

分析

一道比较简单的贪心。

题面很明确地告诉我们，这是一道括号匹配问题。因此我们考虑使用栈模拟。

在模拟时不难发现，只有当栈顶的括号被匹配之后，后面的括号才有可能被匹配。

So，我们只需要优先匹配栈顶括号即可。

剩下的就是模拟了，直接看代码注释吧……

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long 
#define I inline
#define N 1501

using namespace std;


ll n , l[N] , r[N] , p[N];  //p[i]表示左括号i之前有多少括号
char ans[N];
bool flag = true;
stack<int > S;

int main(){
    cin >> n;
    ll cnt = 0; //cnt为当前的括号总数
    for(int i = 1; i <= n; i ++){
        cin >> l[i] >> r[i];
        S.push(i);
        p[i] = cnt;
        ans[++ cnt] = '(';
        while(!S.empty()){
            int top = S.top();
            if(r[top] + p[top] < cnt){  
            //如果当前括号的右端点 + 该括号之前的括号数量小于当前括号总数，则不可能满足
                flag = false;   
                break;
            }
            if(l[top] + p[top] > cnt){
            //如果当前括号左端点 + 该括号之前的括号数量大于当前括号总数，则等待之后的左括号补位。
                break;
            }
            ans[++ cnt] = ')';  //否则就进行匹配
            S.pop();    
        }
    }
    if(S.empty() && flag == true){  //若最后没有未匹配的括号且都可以满足，则当前序列满足条件
        for(int i = 1; i <= n * 2; i ++){
            cout << ans[i];
        }
    }    
    else{
        puts("IMPOSSIBLE");
    }
    return 0;
}

THE END