G_binary_search

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.2 kB
7
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define all(v) v.begin(), v.end()
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define rep(i,a,b) for (int i = a; i < b; i++)
#define vin(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];

typedef vector<int> vi;


void solve(int tc = 0) {
	int n; cin >> n;
	vi a(n), b(n); vin(a, n); vin(b, n);

	auto check = [&](vi v) -> bool{ // checks if v is a subsequence of a 
		int l = 0, r = 0;
		while(l < v.size() and r < a.size()){
			if(v[l] == a[r]){
				l++;
				r++;
				continue;
			}
			r++;
		}
		return r < n;
	};

	auto subsegs = [&](int sz) -> bool{ // generates all possible results after deleting sz elements
		if(sz == 0){
			return b == a;
		}
		for(int start = 0; start < n - sz + 1; start++){
			vi v;
			for(int j = 0; j < n; j++) if(j < start or j >= start + sz) v.pb(b[j]);
			if(check(v)) return true;
		}
		return false;
	};

	int l = 0, r = n;
	while(l < r){
		int m = (l+r)/2;
		if(subsegs(m)){
			r = m;
		}else{
			l = m + 1;
		}
	}
	cout << "Case " << tc+1 << ": " << l << endl;
}

int main() {
	send help
	int tc = 1;
	cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
}
Leave a Comment