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 |
|
|
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 |