Submission #1541847


Source Code Expand

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
  static Scanner sc = new Scanner(System.in);
  static int N;

  public static void main(String[] args) {
    System.out.println(solve());
  }

  static int solve() {
    char[] A = sc.next().toCharArray();
    char[] B = sc.next().toCharArray();
    N = A.length;
    int lastOnePos = N;
    for (int i = N - 1; i >= 0; i--) {
      if (B[i] == '1') {
        lastOnePos = i;
        break;
      }
    }
    if (lastOnePos == N) {
      for (char c : A) {
        if (c == '1') {
          return -1;
        }
      }
      return 0;
    }
    int ans = solve(A, B, lastOnePos);
    for (int i = 0; i < N / 2; i++) {
      char tmp = A[i];
      A[i] = A[N - 1 - i];
      A[N - 1 - i] = tmp;
      tmp = B[i];
      B[i] = B[N - 1 - i];
      B[N - 1 - i] = tmp;
    }
    for (int i = N - 1; i >= 0; i--) {
      if (B[i] == '1') {
        lastOnePos = i;
        break;
      }
    }
    return Math.min(ans, solve(A, B, lastOnePos));
  }

  static int solve(char[] A, char[] B, int lastOnePos) {
    int ans = N;
    for (int i = 0; i < N; i++) {
      if (A[i] != B[i]) ++ans;
    }
    int[] prevPos = new int[N];
    int[] nextPos = new int[N];
    int p = lastOnePos - N;
    for (int i = 0; i < N; i++) {
      if (B[i] == '1') p = i;
      prevPos[i] = p;
    }
    int n = 0;
    while (B[n] == '0') {
      ++n;
    }
    n += N;
    for (int i = N - 1; i >= 0; i--) {
      if (B[i] == '1') n = i;
      nextPos[i] = n;
    }
    ArrayList<Integer> rest = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      rest.clear();
      int diff = 0;
      for (int j = 0; j < N; j++) {
        if (A[j] != B[(j - i + N) % N]) {
          ++diff;
          if (j - prevPos[j] > i) {
            rest.add(((j - prevPos[j] - i) << 16) | (nextPos[j] - j));
          }
        }
      }
      int move;
      if (!rest.isEmpty()) {
        Collections.sort(rest);
        int[] revMax = new int[rest.size() + 1];
        for (int j = rest.size() - 1; j >= 0; j--) {
          revMax[j] = Math.max(revMax[j + 1], rest.get(j) & 0xFFFF);
        }
        move = revMax[0];
        for (int j = 0; j < rest.size(); j++) {
          move = Math.min(move, (rest.get(j) >> 16) + revMax[j + 1]);
        }
      } else {
        move = 0;
      }
//      System.out.println(rest);
//      System.out.println(i + " " + diff + " " + move);
      ans = Math.min(ans, diff + move * 2 + i);
    }
    return ans;
  }

}

Submission Info

Submission Time
Task D - Shift and Flip
User tomerun
Language Java8 (OpenJDK 1.8.0)
Score 1000
Code Size 2628 Byte
Status AC
Exec Time 332 ms
Memory 52364 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 110 ms 22100 KB
sample_02.txt AC 87 ms 19924 KB
sample_03.txt AC 87 ms 21332 KB
sample_04.txt AC 87 ms 19412 KB
subtask_1_01.txt AC 87 ms 19668 KB
subtask_1_02.txt AC 88 ms 19668 KB
subtask_1_03.txt AC 96 ms 18640 KB
subtask_1_04.txt AC 104 ms 19284 KB
subtask_1_05.txt AC 177 ms 21404 KB
subtask_1_06.txt AC 103 ms 18900 KB
subtask_1_07.txt AC 165 ms 22160 KB
subtask_1_08.txt AC 92 ms 20052 KB
subtask_1_09.txt AC 88 ms 19668 KB
subtask_1_10.txt AC 91 ms 19668 KB
subtask_1_11.txt AC 235 ms 23684 KB
subtask_1_12.txt AC 203 ms 22844 KB
subtask_1_13.txt AC 233 ms 22140 KB
subtask_1_14.txt AC 328 ms 42172 KB
subtask_1_15.txt AC 323 ms 40876 KB
subtask_1_16.txt AC 332 ms 38452 KB
subtask_1_17.txt AC 303 ms 34096 KB
subtask_1_18.txt AC 297 ms 29192 KB
subtask_1_19.txt AC 274 ms 24776 KB
subtask_1_20.txt AC 273 ms 24520 KB
subtask_1_21.txt AC 268 ms 42788 KB
subtask_1_22.txt AC 276 ms 42204 KB
subtask_1_23.txt AC 285 ms 49164 KB
subtask_1_24.txt AC 320 ms 52364 KB
subtask_1_25.txt AC 321 ms 51532 KB
subtask_1_26.txt AC 92 ms 21076 KB
subtask_1_27.txt AC 107 ms 20052 KB
subtask_1_28.txt AC 122 ms 20168 KB
subtask_1_29.txt AC 196 ms 22948 KB
subtask_1_30.txt AC 261 ms 24728 KB
subtask_1_31.txt AC 88 ms 21588 KB
subtask_1_32.txt AC 93 ms 19412 KB
subtask_1_33.txt AC 108 ms 22228 KB
subtask_1_34.txt AC 123 ms 21716 KB
subtask_1_35.txt AC 231 ms 24604 KB
subtask_1_36.txt AC 318 ms 28064 KB
subtask_1_37.txt AC 92 ms 20564 KB
subtask_1_38.txt AC 107 ms 20180 KB
subtask_1_39.txt AC 124 ms 20564 KB
subtask_1_40.txt AC 161 ms 22284 KB
subtask_1_41.txt AC 302 ms 26484 KB
subtask_1_42.txt AC 254 ms 26408 KB
subtask_1_43.txt AC 285 ms 28792 KB
subtask_1_44.txt AC 285 ms 30740 KB
subtask_1_45.txt AC 283 ms 25820 KB
subtask_1_46.txt AC 330 ms 25832 KB