A. Math Problem
time limit per test2 seconds memory limit per test256 megabytes
Your math teacher gave you the following problem:
There are n segments on the x-axis, \([l_1; r_1], [l_2; r_2], \ldots, [l_n; r_n]\). The segment [l; r] includes the bounds, i.e. it is a set of such x that \(l \le x \le r\). The length of the segment [l; r] is equal to r - l.
Two segments [a; b] and [c; d] have a common point (intersect) if there exists x that \(a \leq x \leq b and c \leq x \leq d\). For example, [2; 5] and [3; 10] have a common point, but [5; 6] and [1; 4] don't have.
You should add one segment, which has at least one common point with each of the given segments and as short as possible (i.e. has minimal length). The required segment can degenerate to be a point (i.e a segment with length zero). The added segment may or may not be among the given n segments.
In other words, you need to find a segment [a; b], such that [a; b] and every\( [l_i; r_i] \)have a common point for each i, and b-a is minimal.
Input
The first line contains integer number t\( (1 \le t \le 100)\) — the number of test cases in the input. Then t test cases follow.
The first line of each test case contains one integer n \((1 \le n \le 10^{5})\) — the number of segments. The following n lines contain segment descriptions: the i-th of them contains two integers \(l_i,r_i (1 \le l_i \le r_i \le 10^{9})\).
The sum of all values n over all the test cases in the input doesn't exceed \(10^5\).
Output
For each test case, output one integer — the smallest possible length of the segment which has at least one common point with all given segments.
Exampleinput
4 3 4 5 5 9 7 7 5 11 19 4 17 16 16 3 12 14 17 1 1 10 1 1 1
output
2 4 0 0
Note
In the first test case of the example, we can choose the segment [5;7] as the answer. It is the shortest segment that has at least one common point with all given segments.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,l[maxn],r[maxn];
void solve(){
scanf("%d",&n);
int minr=mod,maxl=0;
rep(i,1,n){
int l,r;scanf("%d%d",&l,&r);
minr=min(minr,r);
maxl=max(maxl,l);
}
printf("%d\n",max(maxl-minr,0));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Box
time limit per test1 second memory limit per test256 megabytes
Permutation p is a sequence of integers \(p=[p_1, p_2, \dots, p_n]\), consisting of n distinct (unique) positive integers between 1 and n, inclusive. For example, the following sequences are permutations: [3, 4, 1, 2], [1], [1, 2]. The following sequences are not permutations: [0], [1, 2, 1], [2, 3], [0, 1, 2].
The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation p of length n.
You don't know this permutation, you only know the array q of prefix maximums of this permutation. Formally:
- \(q_1=p_1\),
- \(q_2=\max(p_1, p_2)\),
- \(q_3=\max(p_1, p_2,p_3)\),
- ...
- \(q_n=\max(p_1, p_2,\dots,p_n)\).
You want to construct any possible suitable permutation (i.e. any such permutation, that calculated q for this permutation is equal to the given array).
Input
The first line contains integer number t \((1 \le t \le 10^4)\) — the number of test cases in the input. Then t test cases follow.
The first line of a test case contains one integer n \((1 \le n \le 10^{5})\) — the number of elements in the secret code permutation p.
The second line of a test case contains n integers \(q_1, q_2, \dots, q_n (1 \le q_i \le n)\) — elements of the array q for secret permutation. It is guaranteed that \(q_i \le q_{i+1} for all i (1 \le i < n)\).
The sum of all values n over all the test cases in the input doesn't exceed \(10^5\).
Output
For each test case, print:
- If it's impossible to find such a permutation p, print "-1" (without quotes).
- Otherwise, print n distinct integers \(p_1, p_2, \dots, p_n (1 \le p_i \le n)\). If there are multiple possible answers, you can print any of them.
Exampleinput
4 5 1 3 4 5 5 4 1 1 3 4 2 2 2 1 1
output
1 3 4 5 2 -1 2 1 1
Note
In the first test case of the example answer [1,3,4,5,2] is the only possible answer:
- \(q_{1} = p_{1} = 1\);
- \(q_{2} = \max(p_{1}, p_{2}) = 3\);
- \(q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4\);
- \(q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5\);
- \(q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5\).
It can be proved that there are no answers for the second test case of the example.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,vis[maxn],a[maxn],ans[maxn];
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]),vis[i]=0;
int maxx=a[1],pos=1;
ans[1]=a[1];vis[a[1]]=1;
rep(i,2,n){
if(a[i]<maxx) return (void)puts("-1");
if(a[i]>maxx) ans[i]=a[i];
else{
while(vis[pos]) pos++;
if(pos>maxx) return (void)puts("-1");
ans[i]=pos;
}
vis[ans[i]]=1;
maxx=max(maxx,a[i]);
}
rep(i,1,n) printf("%d ",ans[i]);puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. Messy
time limit per test1 second memory limit per test256 megabytes
You are fed up with your messy room, so you decided to clean it up.
Your room is a bracket sequence \(s=s_{1}s_{2}\dots s_{n}\) of length n. Each character of this string is either an opening bracket '(' or a closing bracket ')'.
In one operation you can choose any consecutive substring of s and reverse it. In other words, you can choose any substring \(s[l \dots r]=s_l, s_{l+1}, \dots, s_r\) and change the order of elements in it into\( s_r, s_{r-1}, \dots, s_{l}\).
For example, if you will decide to reverse substring \(s[2 \dots 4] \)of string s="((()))" it will be equal to s="()(())".
A regular (aka balanced) bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
A prefix of a string s is a substring that starts at position 1. For example, for s="(())()" there are 6 prefixes: "(", "((", "(()", "(())", "(())(" and "(())()".
In your opinion, a neat and clean room s is a bracket sequence that:
- the whole string s is a regular bracket sequence;
- and there are exactly k prefixes of this sequence which are regular (including whole s itself).
For example, if k = 2, then "(())()" is a neat and clean room.
You want to use at most n operations to make your room neat and clean. Operations are applied one after another sequentially.
It is guaranteed that the answer exists. Note that you do not need to minimize the number of operations: find any way to achieve the desired configuration in n or less operations.
Input
The first line contains integer number t \((1 \le t \le 100)\) — the number of test cases in the input. Then t test cases follow.
The first line of a test case contains two integers n and k \((1 \le k \le \frac{n}{2}, 2 \le n \le 2000, n is even)\) — length of s and required number of regular prefixes.
The second line of a test case contains s of length n — the given bracket sequence. It contains only '(' and ')'.
It is guaranteed that there are exactly \frac{n}{2} characters '(' and exactly \(\frac{n}{2}\) characters ')' in the given string.
The sum of all values n over all the test cases in the input doesn't exceed 2000.
Output
For each test case print an answer.
In the first line print integer m \((0 \le m \le n)\) — the number of operations. You do not need to minimize m, any value is suitable.
In the following m lines print description of the operations, each line should contain two integers l,r \((1 \le l \le r \le n)\), representing single reverse operation of \(s[l \dots r]=s_{l}s_{l+1}\dots s_{r}\). Operations are applied one after another sequentially.
The final s after all operations should be a regular, also it should be exactly k prefixes (including s) which are regular.
It is guaranteed that the answer exists. If there are several possible answers you can print any.
Exampleinput
4 8 2 ()(())() 10 3 ))()()()(( 2 1 () 2 1 )(
output
4 3 4 1 1 5 8 2 2 3 4 10 1 4 6 7 0 1 1 2
Note
In the first example, the final sequence is "()(()())", where two prefixes are regular, "()" and "()(()())". Note, that all the operations except "5 8" in the example output are useless (they do not change s).
显然一个合法的括号序列是形如()()()()...(((...)))这样的，那么我只需要用原序列和答案序列去扫，如果遇到了不一样的位置\(pos_i\)，就找到这个位置之后第一个相等的位置\(pos_j\)，然后交换i，j
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,k;
char s[maxn],t[maxn];
vector<pair<int,int> > ans;
void fun(int l,int r){
int mid=(l+r)>>1;
rep(i,l,mid) swap(s[i],s[r-i+l]);
}
void solve(){
scanf("%d%d%s",&n,&k,s+1);
int pos=0,len=n-(k-1)*2;
rep(i,1,k-1) t[++pos]='(',t[++pos]=')';
rep(i,1,len/2) t[++pos]='(';
rep(i,1,len/2) t[++pos]=')';
ans.clear();
rep(i,1,n) if(s[i]!=t[i]){
rep(j,i+1,n) if(s[j]==t[i]){ans.pb({i,j});fun(i,j);break;}
}
printf("%d\n",(int)ans.size());
for(auto [a,b]:ans) printf("%d %d\n",a,b);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
