Submission #1542092


Source Code Expand

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define mp(x, y) make_pair(x, y)
#define fst first
#define snd second
#define pb push_back

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using vii = vector<pii>;
using vvi = vector<vi>;

#define FILE_NAME ""

string a, b;
const int inf = (int)1e9;

bool read() {
  if (!(cin >> a >> b)) {
    return 0;
  }
  return 1;
}

int dist (int from, int to, int n)
{                           
  return (to - from + n) % n;
}

int work (int shift, bool left) {
  string target = a;
  const int n = sz(a);
  const int left_shift = (left ? shift : (n - shift) % n);
  rotate(target.begin(), target.begin() + left_shift, target.end());
  
  vi flip;
  forn (i, n) if (b[i] != a[(i + left_shift) % n])
    flip.pb(i);

  vi next(n), prev(n);  
  int pos = find(all(b), '1') - b.begin();
  assert(pos != n);

  {
    int last = -1;
    forn (i, n) {
      int cur = (i + pos) % n;
      if (b[cur] == '1')
        last = cur;
      prev[cur] = last;
    }
  }

  {
    int last = -1;
    forn (i, n) {
      int cur = (-i + pos + n) % n;
      if (b[cur] == '1')
        last = cur;
      next[cur] = last;
    }

//    copy(all(next), ostream_iterator<int>(cerr, " "));
//    cerr << endl;
  }

  assert(count(all(prev), -1) == 0);
  assert(count(all(next), -1) == 0);

  vii need;
  for (int v : flip) {
    int l = -1, r = -1;
    bool good = false;
    if (!left) {
      l = dist(prev[v], v, n);
      int to = (v + shift) % n;
      r = dist(to, next[to], n);
      if (next[v] != next[to])
        good = true;
    }  
    else {
      int to = (v - shift + n) % n;
      l = dist(prev[to], to, n);
      r = dist(v, next[v], n);
      if (prev[v] != prev[to])
        good = true;
    }

    good = false;
    if (!good)
      need.pb(mp(l, r));
  }

  vi best(n, 0);
  for (const pii &c : need) if (c.fst)
    best[c.fst - 1] = max(best[c.fst - 1], c.snd);

  ford (i, n) if (i + 1 < n)
    best[i] = max(best[i], best[i + 1]);


  int ans = inf;
  forn (i, n)
    ans = min(ans, 2 * (i + best[i]));
  ans += sz(flip) + shift;
                         
  return ans;
}

void solve() {
  const int n = sz(a);
  if (b == string(n, '0')) {
    cout << (a == b ? 0 : -1) << endl;
    return;
  }

  int ans = inf;
  forn (shift, n) forn (i, 2) {
    ans = min(ans, work(shift, i));
  }
  cout << ans << endl;
 // exit(0);
}

int main() {
#ifdef LOCAL
  freopen(FILE_NAME ".in", "r", stdin);
  freopen(FILE_NAME ".out", "w", stdout);
#endif

  ios_base::sync_with_stdio(false);

  while (read()) {
    solve();
  }

#ifdef LOCAL
  cerr << "Time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
  return 0;
}

Submission Info

Submission Time
Task D - Shift and Flip
User Kaban5
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3030 Byte
Status WA
Exec Time 283 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 4
AC × 37
WA × 17
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 255 ms 384 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 149 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt WA 1 ms 256 KB
subtask_1_10.txt WA 2 ms 256 KB
subtask_1_11.txt WA 282 ms 384 KB
subtask_1_12.txt AC 283 ms 384 KB
subtask_1_13.txt AC 281 ms 384 KB
subtask_1_14.txt WA 240 ms 256 KB
subtask_1_15.txt WA 231 ms 256 KB
subtask_1_16.txt WA 235 ms 384 KB
subtask_1_17.txt WA 237 ms 256 KB
subtask_1_18.txt WA 239 ms 256 KB
subtask_1_19.txt WA 255 ms 384 KB
subtask_1_20.txt WA 257 ms 256 KB
subtask_1_21.txt WA 212 ms 256 KB
subtask_1_22.txt WA 216 ms 256 KB
subtask_1_23.txt WA 261 ms 384 KB
subtask_1_24.txt WA 261 ms 384 KB
subtask_1_25.txt WA 261 ms 384 KB
subtask_1_26.txt AC 2 ms 256 KB
subtask_1_27.txt AC 4 ms 256 KB
subtask_1_28.txt AC 16 ms 256 KB
subtask_1_29.txt AC 59 ms 256 KB
subtask_1_30.txt AC 236 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 4 ms 256 KB
subtask_1_34.txt AC 17 ms 256 KB
subtask_1_35.txt WA 60 ms 256 KB
subtask_1_36.txt WA 243 ms 384 KB
subtask_1_37.txt AC 2 ms 256 KB
subtask_1_38.txt AC 4 ms 256 KB
subtask_1_39.txt AC 16 ms 256 KB
subtask_1_40.txt AC 62 ms 256 KB
subtask_1_41.txt AC 230 ms 256 KB
subtask_1_42.txt AC 229 ms 256 KB
subtask_1_43.txt AC 236 ms 256 KB
subtask_1_44.txt AC 242 ms 256 KB
subtask_1_45.txt AC 239 ms 256 KB
subtask_1_46.txt AC 237 ms 256 KB