Submission #5676570

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define mod 1000000007
#define eps 1e-13
#define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define io_file freopen("D:/Coding Problems/Contest/input_file.in", "r", stdin); freopen("D:/Coding Problems/Contest/output_file.out", "w", stdout)

ll modx(ll Base, ll exponent)
{
	ll ans = 1;
	if(Base == 1)
		return Base;
	while(exponent)
	{
		if(exponent & 1)
			ans = (ans * Base)%mod;
		Base = (Base * Base)%mod;
		exponent = exponent >> 1;
	}
	return ans;
}

ll inmodx(ll num)
{
	return (modx(num, mod-2LL));
}

bool cmp(pair < vi, int > a, pair < vi, int > b)//true for a before b
{
	if(a.F.empty())
		return 1;
	if(b.F.empty())
		return 0;
	int i;
	fo(i,0,min(sz(a.F),sz(b.F)))
	{
		if(a.F[i] < b.F[i])
			return 1;
		else if(a.F[i] > b.F[i])
			return 0;
	}
	return (sz(a.F) <= sz(b.F));
}

const int N = (2e3) + 9;
const int M = (N<<2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 900;
const int SQRT = BUCK+9;

const int MAX = 2000;
string a, b;
bitset < MAX > bt[N], prefix[N], suffix[N], dp[N][N], ch;

bool check(int ind, int n)
{
	int i;
	fo(i,0,n)
		if(a[(i+ind)%n] != b[i])
			return 0;
	return 1;
}

void pre(int ind, int n)
{
	int i, j;
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(b[j] == '1')
			bt[ind].set(i);
	}
	return;
}

void pre(int n)
{
	int i, j;
	bt[n] = bt[0];
	prefix[0] = bt[0];
	fo(i,1,n)
		prefix[i] = prefix[i-1]|bt[i];
	suffix[n] = bt[n];
	for(i = n-1; i > 0; i--)
		suffix[i] = suffix[i+1]|bt[i];
	fo(i,0,n+1)
		fo(j,0,n+1)
			dp[i][j] = prefix[i]|suffix[j];
	return;
}

int func(int ind, int n)
{
	int i, j, ans = INF, val, cnt = 0;
	ch.reset();
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] != b[i])
			cnt++;
		if(a[j] == '1' && b[i] == '0')
			ch.set(i);
	}
	j = 1;
	fo(i,0,n)
	{
		if((ch&prefix[i]) == ch)
			val = i + min(abs(ind-i),n-(ind-i));
		else
		{
			while(j < n)
			{
				if((ch&(dp[i][j+1])) != ch)
					break;
				j++;
			}
			val = 2*i + (n-j) + min(abs(ind-j),n-abs(ind-j));
		}
		ans = min(ans, val);
	}
	j = n-1;
	for(i = n; i > 0; i--)
	{
		if((ch&suffix[i]) == ch)
			val = (n-i) + min(abs(ind-i),n-abs(ind-i));
		else
		{
			while(j > 1)
			{
				if((ch&(dp[j-1][i])) != ch)
					break;
				j--;
			}
			val = 2*(n-i) + j + min(abs(ind-j),n-abs(ind-j));
		}
		ans = min(ans, val);
	}
	ans += cnt;
	return ans;
}

void solve()
{
	int n, i, ans = INF;
	bool has1 = 0;
	cin >> a;
	cin >> b;
	n = a.length();
	for(auto x : b)
		has1 |= (x == '1');
	if(!has1)
	{
		fo(i,0,n)
			if(check(i,n))
				ans = min(ans, min(i,n-i));
		if(ans == INF)
			ans = -1;
		cout << ans << '\n';
		return;
	}
	if(n == 1)
	{
		if(a == b)
			cout << 0 << '\n';
		else
			cout << 1 << '\n';
		return;
	}
	fo(i,0,n)
		pre(i,n);
	pre(n);
	fo(i,0,n)
		ans = min(ans, func(i,n));
	cout << ans << '\n';
	return;
}

int main()
{
	sws;
	clock_t clk;
	clk = clock();
	// io_file;
	// srand (time(NULL));

	//Code here
	int t = 1, cs;
	cout << fixed << setprecision(15);
	// cin >> t;
	fo(cs,1,t+1)
	{
		// cout << "Case #" << cs << ": ";
		solve();
	}
	// Code ends here

	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
	return 0;
}

Submission Info

Judge Result