Submission #5798576


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;
int prefix[N], suffix[N];
set < pii > st;
vi arr_prefix[N], arr_suffix[N];

void pre(int ind, int n)
{
	int i, j;
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(b[j] == '1')
		{
			prefix[i] = min(prefix[i], ind);
			suffix[i] = max(suffix[i], (ind == 0) ? n : ind);
		}
	}
	return;
}

int func(int ind, int n)
{
	int i, j, ans = INF, val, cnt = 0;
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] != b[i])
			cnt++;
	}
	st.clear();
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] == '1' && b[i] == '0')
			st.insert({suffix[i],i});
	}
	fo(i,0,n)
	{
		// st.erase({suffix[i],i});
		for(auto x : arr_prefix[i])
			st.erase({suffix[x],x});
		if(st.empty())
			val = i + min(abs(ind-i),n-(ind-i));
		else
		{
			j = st.begin()->F;
			val = 2*i + (n-j) + min(abs(ind-j),n-abs(ind-j));
		}
		ans = min(ans, val);
	}
	st.clear();
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] == '1' && b[i] == '0')
			st.insert({-prefix[i],(i == 0) ? n : i});
	}
	for(i = n; i > 0; i--)
	{
		// st.erase({-prefix[i],i});
		for(auto x : arr_suffix[i])
			st.erase({-prefix[x],x});
		if(st.empty())
			val = (n-i) + min(abs(ind-i),n-abs(ind-i));
		else
		{
			j = -st.begin()->F;
			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)
	{
		if(a == b)
			cout << 0 << '\n';
		else
			cout << -1 << '\n';
		return;
	}
	if(n == 1)
	{
		if(a == b)
			cout << 0 << '\n';
		else
			cout << 1 << '\n';
		return;
	}
	fo(i,0,n)
	{
		prefix[i] = INF;
		suffix[i] = -INF;
	}
	fo(i,0,n)
		pre(i,n);
	suffix[n] = suffix[0];
	prefix[n] = prefix[0];
	fo(i,0,n+1)
	{
		arr_prefix[prefix[i]].pb(i);
		arr_suffix[suffix[i]].pb(i);
	}
	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

Submission Time
Task D - Shift and Flip
User vjudge3
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 3895 Byte
Status AC
Exec Time 1267 ms
Memory 640 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 4
AC × 54
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 384 KB
sample_02.txt AC 1 ms 384 KB
sample_03.txt AC 1 ms 384 KB
sample_04.txt AC 1 ms 384 KB
subtask_1_01.txt AC 1 ms 384 KB
subtask_1_02.txt AC 1 ms 384 KB
subtask_1_03.txt AC 1 ms 384 KB
subtask_1_04.txt AC 1 ms 384 KB
subtask_1_05.txt AC 150 ms 384 KB
subtask_1_06.txt AC 1 ms 384 KB
subtask_1_07.txt AC 154 ms 384 KB
subtask_1_08.txt AC 1 ms 384 KB
subtask_1_09.txt AC 1 ms 384 KB
subtask_1_10.txt AC 3 ms 384 KB
subtask_1_11.txt AC 745 ms 384 KB
subtask_1_12.txt AC 459 ms 384 KB
subtask_1_13.txt AC 752 ms 384 KB
subtask_1_14.txt AC 744 ms 512 KB
subtask_1_15.txt AC 845 ms 512 KB
subtask_1_16.txt AC 1038 ms 512 KB
subtask_1_17.txt AC 1056 ms 512 KB
subtask_1_18.txt AC 1223 ms 512 KB
subtask_1_19.txt AC 1267 ms 512 KB
subtask_1_20.txt AC 1196 ms 512 KB
subtask_1_21.txt AC 688 ms 512 KB
subtask_1_22.txt AC 689 ms 512 KB
subtask_1_23.txt AC 1042 ms 640 KB
subtask_1_24.txt AC 1038 ms 640 KB
subtask_1_25.txt AC 1035 ms 640 KB
subtask_1_26.txt AC 3 ms 384 KB
subtask_1_27.txt AC 7 ms 384 KB
subtask_1_28.txt AC 34 ms 384 KB
subtask_1_29.txt AC 147 ms 384 KB
subtask_1_30.txt AC 637 ms 512 KB
subtask_1_31.txt AC 1 ms 384 KB
subtask_1_32.txt AC 3 ms 384 KB
subtask_1_33.txt AC 7 ms 384 KB
subtask_1_34.txt AC 40 ms 384 KB
subtask_1_35.txt AC 158 ms 384 KB
subtask_1_36.txt AC 692 ms 512 KB
subtask_1_37.txt AC 3 ms 384 KB
subtask_1_38.txt AC 7 ms 384 KB
subtask_1_39.txt AC 40 ms 384 KB
subtask_1_40.txt AC 167 ms 384 KB
subtask_1_41.txt AC 677 ms 384 KB
subtask_1_42.txt AC 667 ms 512 KB
subtask_1_43.txt AC 682 ms 512 KB
subtask_1_44.txt AC 716 ms 384 KB
subtask_1_45.txt AC 679 ms 384 KB
subtask_1_46.txt AC 695 ms 512 KB