Submission #1543299
Source Code Expand
#pragma region Template
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <stack>
#include <set>
#include <algorithm>
#include <bitset>
#include <functional>
#include <ctime>
#include <cassert>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <complex>
#include <regex>
#include <numeric>
#pragma comment(linker, "/STACK:167772160")
using namespace std;
#define mp make_pair
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define print_var(x) cerr << #x << " : " << (x) << endl
#define print_array(arr, len) {cerr << #arr << " : "; for(int i = 0; i < len; ++i) cerr << arr[i] << ' '; cerr << endl;}
#define print_2d_array(arr, len1, len2) {cerr << #arr << endl; for(int i = 0; i < len1; ++i, cerr << endl) for(int j = 0; j < len2; ++j) cerr << arr[i][j] << ' ';}
#define print_iterable(i) {cerr << #i << " : "; for(auto e : i) cerr << e << ' '; cerr << endl;}
#define print_new_line() cerr << endl
template <typename T, typename Q>
void print_pair1(pair<T, Q> x)
{
cerr << "(" << x.first << ", " << x.second << ")\n";
}
#define print_pair(x) {cerr << #x << " : "; print_pair1(x);}
#else
#define print_pair(x) (void)0
#define eprintf(...) (void)0
#define print_var(x) (void)0
#define print_array(arr, len) {}
#define print_2d_array(arr, len1, len2) {}
#define print_iterable(i) {}
#define print_new_line() (void)0
#endif
#define rand govno_ebanoe
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = (int)1e9 + 10;
const ll LINF = ll(2e18) + 10;
const double PI = acosl(-1);
const double eps = 1e-8;
const ld EPS = 1e-12;
#pragma endregion
#ifdef LOCAL
#define ERR_CATCH
//#define NOERR
#endif
const int N = 6010;
int n;
string a, b;
char buf[N];
int ps[N];
int to_l[N], to_r[N];
int smax[N];
string read()
{
scanf("%s", buf);
return buf;
}
void solve()
{
a = read();
b = read();
if (a == b)
{
puts("0");
return;
}
n = a.size();
bool oneb = false;
for (auto& e : a)
e -= '0';
for (auto& e : b)
{
e -= '0';
if (e)
oneb = true;
}
if (!oneb)
{
puts("-1");
return;
}
int res = 10 * n;
b = b + b + b;
partial_sum(b.begin(), b.end(), ps);
for(int i = n; i < 2 * n; ++i)
{
int x = i;
while (!b[x])
--x;
to_l[i] = i - x;
x = i;
while (!b[x])
++x;
to_r[i] = x - i;
}
copy(to_l + n, to_l + 2 * n, to_l);
copy(to_l + n, to_l + 2 * n, to_l + 2 * n);
copy(to_r + n, to_r + 2 * n, to_r);
copy(to_r + n, to_r + 2 * n, to_r + 2 * n);
for(int sh = -n + 1; sh <= n - 1; ++sh)
{
auto tres = abs(sh);
vector<pii> go;
for(int i = 0; i < n; ++i)
if (a[i] != b[i + n + sh])
{
++tres;
auto f = (i + n);
auto s = (i + n + sh);
if (f > s)
swap(f, s);
if (ps[s] - ps[f - 1] == 0) // no ones
go.emplace_back(to_l[f], to_r[s]);
}
if (go.size() > 0)
{
sort(go.begin(), go.end());
smax[go.size()] = 0;
for (int i = (int)go.size() - 1; i >= 0; --i)
smax[i] = max(smax[i + 1], go[i].second);
int add = smax[0];
for (int i = 0; i < go.size(); ++i)
add = min(add, go[i].first + smax[i + 1]);
tres += 2 * add;
}
res = min(res, tres);
}
printf("%d\n", res);
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef NOERR
freopen("err.txt", "w", stderr);
#endif
#else
//freopen("knight.in", "r", stdin);
//freopen("knight.out", "w", stdout);
#endif
#ifdef ERR_CATCH
try
{
#endif
#ifdef ST
while (true)
solve();
#endif
#ifdef CASES
#define MULTITEST
#endif
#ifdef MULTITEST
int t;
scanf("%d", &t);
char endl1[5];
fgets(endl1, 5, stdin);
for (int i = 0; i < t; ++i)
{
#ifdef CASES
printf("Case #%d: ", i + 1);
#endif
solve();
#ifdef CASES
eprintf("Passed case #%d:\n", i + 1);
#endif
}
#else
solve();
#endif
#ifdef ERR_CATCH
}
catch (logic_error e)
{
print_var(e.what());
puts("___________________________________________________________________________");
exit(0);
}
#endif
#ifdef LOCAL
eprintf("\n\nTime: %.3lf\n", double(clock()) / CLOCKS_PER_SEC);
#endif
}
Submission Info
Submission Time
2017-08-26 22:35:35+0900
Task
D - Shift and Flip
User
tinsane
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
4600 Byte
Status
AC
Exec Time
104 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘std::string read()’:
./Main.cpp:89:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
^
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
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
21 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
1 ms
256 KB
subtask_1_11.txt
AC
57 ms
384 KB
subtask_1_12.txt
AC
55 ms
384 KB
subtask_1_13.txt
AC
57 ms
384 KB
subtask_1_14.txt
AC
96 ms
384 KB
subtask_1_15.txt
AC
80 ms
384 KB
subtask_1_16.txt
AC
62 ms
384 KB
subtask_1_17.txt
AC
58 ms
384 KB
subtask_1_18.txt
AC
51 ms
384 KB
subtask_1_19.txt
AC
50 ms
384 KB
subtask_1_20.txt
AC
51 ms
384 KB
subtask_1_21.txt
AC
62 ms
384 KB
subtask_1_22.txt
AC
62 ms
384 KB
subtask_1_23.txt
AC
104 ms
384 KB
subtask_1_24.txt
AC
104 ms
384 KB
subtask_1_25.txt
AC
104 ms
384 KB
subtask_1_26.txt
AC
1 ms
256 KB
subtask_1_27.txt
AC
2 ms
256 KB
subtask_1_28.txt
AC
3 ms
256 KB
subtask_1_29.txt
AC
10 ms
256 KB
subtask_1_30.txt
AC
41 ms
384 KB
subtask_1_31.txt
AC
1 ms
256 KB
subtask_1_32.txt
AC
1 ms
256 KB
subtask_1_33.txt
AC
2 ms
256 KB
subtask_1_34.txt
AC
4 ms
256 KB
subtask_1_35.txt
AC
10 ms
256 KB
subtask_1_36.txt
AC
43 ms
384 KB
subtask_1_37.txt
AC
1 ms
256 KB
subtask_1_38.txt
AC
2 ms
256 KB
subtask_1_39.txt
AC
3 ms
256 KB
subtask_1_40.txt
AC
11 ms
256 KB
subtask_1_41.txt
AC
41 ms
384 KB
subtask_1_42.txt
AC
40 ms
384 KB
subtask_1_43.txt
AC
40 ms
384 KB
subtask_1_44.txt
AC
44 ms
384 KB
subtask_1_45.txt
AC
43 ms
384 KB
subtask_1_46.txt
AC
43 ms
384 KB