Codeforces Round #620 (Div. 2)D（LIS，构造）

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int ans[200007];
 5 int ans2[200007];
 6 int main(){
 7     ios::sync_with_stdio(false);
 8     cin.tie(NULL);
 9     cout.tie(NULL);
10     int t;
11     cin>>t;
12     while(t--){
13         int n;
14         string s;
15         cin>>n>>s;
16         int mx=n;
17         for(int i=0;i<n;++i){
18             int cnt=1;
19             while(i<n&&s[i]==‘<‘){
20                 ++cnt;
21                 ++i;
22             }
23             for(int j=i;j>i-cnt;--j){
24                 ans[j]=mx;//尽可能将大的数放在前面
25                 --mx;
26             }
27         }
28         int mn=1;
29         for(int i=0;i<n;++i){
30             int cnt=1;
31             while(i<n&&s[i]==‘>‘){
32                 ++cnt;
33                 ++i;
34             }
35             for(int j=i;j>i-cnt;--j){
36                 ans2[j]=mn;//尽可能将小的数放在前面
37                 ++mn;
38             }
39         }
40         for(int i=0;i<n;++i)
41             cout<<ans[i]<<" ";
42         cout<<"\n";
43         for(int i=0;i<n;++i)
44             cout<<ans2[i]<<" ";
45         cout<<"\n";
46     }
47     return 0;
48 }