Codeforces Round 873 (Div. 1) 1827A. Counting Orders Solution

 

Problem Link:  https://codeforces.com/problemset/problem/1827/A

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. const int mod = 1e9 + 7 ;
5. int32_t main() {
6. ios_base::sync_with_stdio(0);
7. cin.tie(0);
8. int t;
9. cin >> t;
10. while (t--) {
11. int n ; cin >> n ;
12. vector<int>a(n),b(n) ;
13. for ( int i = 0 ; i < n ; i++){
14. cin >> a[i] ;
15. }
16. for ( int i = 0 ; i < n ; i++){
17. cin >> b[i] ;
18. }
19. sort(a.begin(),a.end()) ;
20. sort(b.begin(),b.end()) ;
21. long long ans = - 1;
22. for ( int i = 0 ; i < n ; i++){
23. if(a[i] <= b[i]){
24. ans = 0 ;
25. break ;
26. }
27. }
28. if(ans == 0){
29. cout <<0<<'\n';
30. continue ;
31. }
32. ans = 1 ;
33. for ( int i = 0 ; i < n ; i++){
34. int low = i , high = n - 1 ;
35. int index ;
36. while(low <= high){
37. int mid = low + ( ( high - low ) / 2 );
38. if( a[i] > b[mid] ){
39. index = mid ;
40. low = mid + 1 ;
41. }
42. else {
43. high = mid - 1 ;
44. }
45. }
46. long long value = index - i + 1 ;
47. ans *= value ;
48. ans %= mod ;
49. }
50. cout <<ans <<'\n';
51. }
52. return 0 ;
53. }