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