Submission #1543771


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>;
using vc = vector<char>;

#define FILE_NAME ""

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

#define TEST 0

mt19937 rng;

string rand_string (int n) {
  string ans(n, '0');
  forn (i, n)
    ans[i] = rng() % 2 + '0';
  return ans;
}

bool read() {
#if !TEST
  if (!(cin >> a >> b)) {
    return 0;
  }
  return 1;
#else
  int n = rng() % 10 + 1;
  a = rand_string(n);
  b = rand_string(n);
  return 1;
#endif
}

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

int code (const string &s) {
  int ans = 0;
  for (char ch : s)
    ans *= 2, ans += ch - '0';
  return ans;
}

int brut () {
  const int n = sz(b);
  
  vi dist(1 << n, -1);
  queue<int> q;
  
  int acode = code(a), bcode = code(b);
  dist[acode] = 0; q.push(acode);
  
  while (!q.empty()) {
    int cur = q.front(); q.pop();
    forn (i, n) if ((bcode >> i) & 1)
    {
      int to = (cur ^ (1 << i));
      if (dist[to] == -1) {
        dist[to] = dist[cur] + 1;
        q.push(to);
      }
    }

    {                                             
      int to = (cur >> 1) ^ ((cur & 1) << (n - 1));
//      cerr << bitset<5>(cur) << ' ' << bitset<5>(to) << endl;      
      if (dist[to] == -1) {
        dist[to] = dist[cur] + 1;
        q.push(to);
      }
    }

    {
      int to = ((cur << 1) & ((1 << n) - 1)) ^ ((cur & (1 << (n - 1))) >> (n - 1));
//      cerr << bitset<5>(cur) << ' ' << bitset<5>(to) << endl;
      if (dist[to] == -1) {
        dist[to] = dist[cur] + 1;
        q.push(to);
      }
    }
  }

  return dist[bcode];
}

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

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

  vi sum(2 * n + 2);
  forn (i, sz(sum) - 1) 
    sum[i + 1] = sum[i] + (b[i % n] == '1');

  auto cnt = [&] (int l, int r) -> int
  {
    while (r < l)
      r += n;
    return sum[r + 1] - sum[l];
  };

  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 (cnt(v, to))
        good = true;
    }  
    else {
      int to = (v - shift + n) % n;
      l = dist(prev[to], to, n);
      r = dist(v, next[v], n);
      if (cnt(to, v))
        good = true;
    }
/*
    if (b == "0010000" && shift == 5 && !left) {
      cerr << l << ' ' << r << endl;
      cerr << v << ' ' << (v + shift) % n << endl;
      
      bool bgood = false;
      for (int u = v; u != (v + shift) % n; u = (u + 1) % n)
        bgood |= (b[u] == '1');
      bgood |= (b[(v + shift) % n] == '1');
      assert(bgood == good);    
    }
*/
    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;

  if (b == "0010000" && shift == 5 && !left) {
    cerr << ans << endl;
  }
                        
  return ans;
}

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

  int ans = inf;
  forn (shift, n) forn (i, 2) {
    ans = min(ans, work(shift, i));
  }
  return ans;
}

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()) {
    int my = solve();
    cout << my << endl;
    /*
    int br = brut();
    if (my != br)
    {
      cerr << a << ' ' << b << endl;
      cerr << my << ' ' << br << endl;
    }
    assert(my == br);
    */
  }

#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 1000
Code Size 5182 Byte
Status AC
Exec Time 303 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 255 ms 384 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 208 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 285 ms 384 KB
subtask_1_12.txt AC 285 ms 384 KB
subtask_1_13.txt AC 285 ms 384 KB
subtask_1_14.txt AC 303 ms 384 KB
subtask_1_15.txt AC 295 ms 384 KB
subtask_1_16.txt AC 288 ms 384 KB
subtask_1_17.txt AC 287 ms 384 KB
subtask_1_18.txt AC 285 ms 384 KB
subtask_1_19.txt AC 285 ms 384 KB
subtask_1_20.txt AC 282 ms 384 KB
subtask_1_21.txt AC 255 ms 384 KB
subtask_1_22.txt AC 255 ms 384 KB
subtask_1_23.txt AC 294 ms 384 KB
subtask_1_24.txt AC 294 ms 384 KB
subtask_1_25.txt AC 294 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 18 ms 256 KB
subtask_1_29.txt AC 69 ms 256 KB
subtask_1_30.txt AC 271 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 19 ms 256 KB
subtask_1_35.txt AC 68 ms 256 KB
subtask_1_36.txt AC 274 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 18 ms 256 KB
subtask_1_40.txt AC 70 ms 256 KB
subtask_1_41.txt AC 268 ms 384 KB
subtask_1_42.txt AC 268 ms 384 KB
subtask_1_43.txt AC 270 ms 384 KB
subtask_1_44.txt AC 275 ms 384 KB
subtask_1_45.txt AC 273 ms 384 KB
subtask_1_46.txt AC 273 ms 384 KB