Submission #1546711


Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define fio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

const int N = 4005;
string a,b;
int n;

int pl[N],pr[N];
int pfl[N],pfr[N];

vector<pii> v;

int main() {
	fio;
	cin >> a >> b;
	if(a==b) {
		printf("0\n");
		return 0;
	}
	n = a.size();
	int last = -1;
	for(int i = 0; i < 2*n; ++i) {
		if(b[i%n] == '1')
			last = i;
		if(i >= n)
			pl[i-n] = i-last;
	}
	if(last == -1) {
		printf("-1\n");
		return 0;
	}
	last = 2*n;
	for(int i = 2*n-1; i >= 0; --i) {
		if(b[i%n] == '1')
			last = i;
		if(i < n)
			pr[i] = last-i;
	}

	int ans = 1<<26;
	for(int s = 1-n; s < n; ++s) {
		string c = a;
		for(int i = 0; i < n; ++i) {
			int j = (i+s+n)%n;
			c[i] = a[j];
		}
		v.clear();
		for(int i = 0; i < n; ++i) {
			if(c[i] != b[i]) {
				v.emplace_back(pl[i],pr[i]);
			}
		}
		int base_l=0,base_r=0;
		if(s < 0) base_l = -s;
		if(s > 0) base_r = s;
		sort(v.begin(),v.end());
		pfl[0] = pfr[0] = 0;
		for(int i = 1; i <= v.size(); ++i) {
			pfl[i] = max(pfl[i-1],v[i-1].fi);
			pfr[i] = max(pfr[i-1],v[v.size()-i].se);

		}

		//iter on max l
		for(int i = 0; i <= v.size(); ++i) {
			int max_l = pfl[i], max_r = pfr[v.size()-i];
			int r = v.size();
			r += 2*(max(base_r,max_r) - base_r);
			r += base_r;
			r += 2*(max(base_l,max_l) - base_l);
			r += base_l;
			ans = min(ans,r);
		}
	}
	printf("%d\n",ans);
}

Submission Info

Submission Time
Task D - Shift and Flip
User cephian
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1599 Byte
Status AC
Exec Time 300 ms
Memory 384 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 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 189 ms 384 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 2 ms 256 KB
subtask_1_11.txt AC 231 ms 384 KB
subtask_1_12.txt AC 199 ms 384 KB
subtask_1_13.txt AC 237 ms 384 KB
subtask_1_14.txt AC 206 ms 384 KB
subtask_1_15.txt AC 233 ms 384 KB
subtask_1_16.txt AC 224 ms 384 KB
subtask_1_17.txt AC 235 ms 384 KB
subtask_1_18.txt AC 275 ms 384 KB
subtask_1_19.txt AC 300 ms 384 KB
subtask_1_20.txt AC 299 ms 384 KB
subtask_1_21.txt AC 128 ms 384 KB
subtask_1_22.txt AC 127 ms 384 KB
subtask_1_23.txt AC 195 ms 384 KB
subtask_1_24.txt AC 195 ms 384 KB
subtask_1_25.txt AC 196 ms 384 KB
subtask_1_26.txt AC 2 ms 256 KB
subtask_1_27.txt AC 3 ms 256 KB
subtask_1_28.txt AC 10 ms 256 KB
subtask_1_29.txt AC 42 ms 256 KB
subtask_1_30.txt AC 180 ms 384 KB
subtask_1_31.txt AC 1 ms 256 KB
subtask_1_32.txt AC 2 ms 256 KB
subtask_1_33.txt AC 3 ms 256 KB
subtask_1_34.txt AC 12 ms 256 KB
subtask_1_35.txt AC 41 ms 256 KB
subtask_1_36.txt AC 186 ms 384 KB
subtask_1_37.txt AC 2 ms 256 KB
subtask_1_38.txt AC 3 ms 256 KB
subtask_1_39.txt AC 11 ms 256 KB
subtask_1_40.txt AC 46 ms 256 KB
subtask_1_41.txt AC 176 ms 384 KB
subtask_1_42.txt AC 173 ms 384 KB
subtask_1_43.txt AC 181 ms 384 KB
subtask_1_44.txt AC 189 ms 384 KB
subtask_1_45.txt AC 190 ms 384 KB
subtask_1_46.txt AC 193 ms 384 KB