fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29.  
  30. vector<int> a;
  31. vector<int> b;
  32.  
  33. //* Checking whether a occurs in subseq of b 
  34. int subsequence(int s, int e, int n){
  35.  
  36. 	int j = s;
  37. 	int i = 0;
  38. 	int ct = 0;
  39.  
  40. 	while(i<n && j<=e){
  41. 		while(i<n && b[i] != a[j]) i++;
  42. 		if(i==n) break;
  43.  
  44. 		ct++;
  45. 		i++;
  46. 		j++;
  47. 	}
  48.  
  49. 	return ct;
  50. }
  51.  
  52. int consistency1(int n){
  53.  
  54. 	int maxi = 0;
  55.  
  56. 	for(int i=0; i<n; i++){
  57. 		for(int j=i; j<n; j++){
  58. 			int ct = subsequence(i, j, n);
  59. 			maxi = max(maxi, ct);
  60. 		}
  61. 	}
  62.  
  63. 	return n-maxi;
  64. }
  65.  
  66.  
  67.  
  68.  
  69.  
  70. int consistency2(int n){
  71.  
  72. 	int maxi = 0;
  73.  
  74. 	for(int i=0; i<n; i++){
  75.  
  76. 		int j = i;
  77. 		int k = 0;
  78. 		int ct = 0;
  79.  
  80. 		while(j<n){
  81. 			while(k<n && b[k] != a[j]) k++;
  82. 			if(k==n) break;
  83.  
  84. 			ct++;
  85. 			j++;
  86. 			k++;
  87. 		}
  88.  
  89. 		maxi = max(maxi, ct);
  90. 	}
  91.  
  92.  
  93.  
  94. 	return n-maxi;
  95.  
  96. }
  97.  
  98.  
  99.  
  100.  
  101.  
  102. int consistency3(int n){
  103.  
  104. 	unordered_map<int,int> mp;
  105. 	for(int i=0; i<n; i++) mp[b[i]] = i;
  106.  
  107. 	int maxi = 0;
  108.  
  109. 	int i = 0;
  110. 	while(i<n){
  111.  
  112. 		int j = i+1;
  113.  
  114. 		while(j<n && mp[a[j]] > mp[a[j-1]]) j++;
  115.  
  116. 		maxi = max(maxi, j-i);
  117. 		i = j;
  118. 	}
  119.  
  120. 	return n-maxi;
  121. }
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138. int practice(int n){
  139.  
  140.  
  141.     return 0;
  142. }
  143.  
  144.  
  145.  
  146.  
  147.  
  148. void solve() {
  149.  
  150.     int n;
  151.     cin>> n;
  152.  
  153.     a.resize(n);
  154.     for(int i=0; i<n; i++) cin >> a[i];
  155.  
  156.     b.resize(n);
  157.     for(int i=0; i<n; i++) cin >> b[i];
  158.  
  159.  
  160.     cout << consistency1(n) << " " << consistency2(n) << " " << consistency3(n) << endl;
  161.  
  162.  
  163. }
  164.  
  165.  
  166.  
  167.  
  168.  
  169. int32_t main() {
  170.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  171.  
  172.     int t = 1;
  173.     // cin >> t;
  174.     while (t--) {
  175.         solve();
  176.     }
  177.  
  178.     return 0;
  179. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
8
4 2 3 1 5 7 6 8
3 1 4 7 6 2 8 5
stdout
copy 
5 5 5
https://ideone.com/NMc2ja
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!