Submission #1547100
Source Code Expand
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { new Main().go(); } PrintWriter out; Reader in; BufferedReader br; Main() throws IOException { try { //br = new BufferedReader( new FileReader("input.txt") ); in = new Reader("input.txt"); out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) ); } catch (Exception e) { //br = new BufferedReader( new InputStreamReader( System.in ) ); in = new Reader(); out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) ); } } void go() throws IOException { int t = 1; while (t > 0) { solve(); //out.println(); t--; } out.flush(); out.close(); } int inf = 2000000000; int mod = 1000000007; double eps = 0.00000001; int n; int m; //ArrayList<Pair>[] g = new ArrayList[2000000]; void solve() throws IOException { String s1 = in.next(); String s2 = in.next(); if (!s1.equals(s2) && s2.indexOf('1') < 0) { System.out.println(-1); return; } if (s1.equals(s2)) { System.out.println(0); return; } int n = s1.length(); int[] a = new int[n]; int[] b = new int[n]; int[] ra = new int[n]; int[] rb = new int[n]; for (int i = 0; i < n; i++) { a[i] = s1.charAt(i) - '0'; b[i] = s2.charAt(i) - '0'; } for (int i = 0; i < n; i++) { ra[i] = s1.charAt(n-i-1) - '0'; rb[i] = s2.charAt(n-i-1) - '0'; } out.println(Math.min(f(a, b), f(ra, rb))); } long f(int[] a, int[] b) { int n = a.length; int[] c = new int[n]; int fp = 0; long ans = Long.MAX_VALUE; int[] r = new int[n]; for (int i = 0; i < n; i++) { int sum = 0; for (int j = 0; j < n; j++) if (a[j] != b[(j+i)%n]) sum++; r[i] = sum; } while (b[fp] != 1) fp++; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) if (b[j] == 1) c[j] = -1; int last = -1; long sum; int maxmove = 0; for (int j = n-1; j >= 0; j--) { if (b[j] == 1) { last = j; } if (c[j] != -1 && a[j] == 1 && b[j] == 0) { if (last == -1) { maxmove = Math.max(maxmove, fp + n-j); } else { maxmove = Math.max(maxmove, last - j); } } } for (int k = 0; k < n; k++) { if (k >= maxmove) { sum = r[((k-i)%n+n)%n]; } else { sum = r[((k-i)%n+n)%n] + (maxmove - k)*2; } ans = Math.min(ans, k+sum+i); } //System.err.println(i+" "+maxmove+" "+ans); int first = a[0]; int first2 = c[0]; for (int j = 0; j < n-1; j++) { a[j] = a[j+1]; c[j] = c[j+1]; } a[n-1] = first; c[n-1] = first2; } return ans; } class Pair implements Comparable<Pair>{ int a; int b; Pair(int a, int b) { this.a = a; this.b = b; } public int compareTo(Pair p) { if (a > p.a) return 1; if (a < p.a) return -1; if (b > p.b) return 1; if (b < p.b) return -1; return 0; } } class Item { int a; int b; int c; Item(int a, int b, int c) { this.a = a; this.b = b; this.c = c; } } class Reader { BufferedReader br; StringTokenizer tok; Reader(String file) throws IOException { br = new BufferedReader( new FileReader(file) ); } Reader() throws IOException { br = new BufferedReader( new InputStreamReader(System.in) ); } String next() throws IOException { while (tok == null || !tok.hasMoreElements()) tok = new StringTokenizer(br.readLine()); return tok.nextToken(); } int nextInt() throws NumberFormatException, IOException { return Integer.valueOf(next()); } long nextLong() throws NumberFormatException, IOException { return Long.valueOf(next()); } double nextDouble() throws NumberFormatException, IOException { return Double.valueOf(next()); } String nextLine() throws IOException { return br.readLine(); } } }
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | mikcorer |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1000 |
Code Size | 5428 Byte |
Status | AC |
Exec Time | 325 ms |
Memory | 25260 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 | 71 ms | 19408 KB |
sample_02.txt | AC | 72 ms | 20820 KB |
sample_03.txt | AC | 71 ms | 20564 KB |
sample_04.txt | AC | 71 ms | 19284 KB |
subtask_1_01.txt | AC | 72 ms | 21072 KB |
subtask_1_02.txt | AC | 71 ms | 21204 KB |
subtask_1_03.txt | AC | 70 ms | 20944 KB |
subtask_1_04.txt | AC | 73 ms | 18388 KB |
subtask_1_05.txt | AC | 266 ms | 23868 KB |
subtask_1_06.txt | AC | 76 ms | 18388 KB |
subtask_1_07.txt | AC | 82 ms | 19920 KB |
subtask_1_08.txt | AC | 71 ms | 19284 KB |
subtask_1_09.txt | AC | 70 ms | 15700 KB |
subtask_1_10.txt | AC | 75 ms | 21452 KB |
subtask_1_11.txt | AC | 255 ms | 20836 KB |
subtask_1_12.txt | AC | 241 ms | 25260 KB |
subtask_1_13.txt | AC | 267 ms | 23000 KB |
subtask_1_14.txt | AC | 248 ms | 21984 KB |
subtask_1_15.txt | AC | 234 ms | 18916 KB |
subtask_1_16.txt | AC | 249 ms | 22336 KB |
subtask_1_17.txt | AC | 252 ms | 22212 KB |
subtask_1_18.txt | AC | 275 ms | 21264 KB |
subtask_1_19.txt | AC | 257 ms | 22776 KB |
subtask_1_20.txt | AC | 247 ms | 22752 KB |
subtask_1_21.txt | AC | 246 ms | 20860 KB |
subtask_1_22.txt | AC | 269 ms | 23560 KB |
subtask_1_23.txt | AC | 320 ms | 22508 KB |
subtask_1_24.txt | AC | 324 ms | 21508 KB |
subtask_1_25.txt | AC | 325 ms | 23344 KB |
subtask_1_26.txt | AC | 93 ms | 18256 KB |
subtask_1_27.txt | AC | 91 ms | 19920 KB |
subtask_1_28.txt | AC | 114 ms | 20380 KB |
subtask_1_29.txt | AC | 189 ms | 19500 KB |
subtask_1_30.txt | AC | 243 ms | 21268 KB |
subtask_1_31.txt | AC | 70 ms | 18260 KB |
subtask_1_32.txt | AC | 82 ms | 19280 KB |
subtask_1_33.txt | AC | 91 ms | 21712 KB |
subtask_1_34.txt | AC | 122 ms | 20948 KB |
subtask_1_35.txt | AC | 155 ms | 21780 KB |
subtask_1_36.txt | AC | 240 ms | 22896 KB |
subtask_1_37.txt | AC | 76 ms | 19408 KB |
subtask_1_38.txt | AC | 92 ms | 22996 KB |
subtask_1_39.txt | AC | 114 ms | 20368 KB |
subtask_1_40.txt | AC | 173 ms | 18988 KB |
subtask_1_41.txt | AC | 244 ms | 21016 KB |
subtask_1_42.txt | AC | 243 ms | 22848 KB |
subtask_1_43.txt | AC | 236 ms | 22336 KB |
subtask_1_44.txt | AC | 267 ms | 23548 KB |
subtask_1_45.txt | AC | 260 ms | 19584 KB |
subtask_1_46.txt | AC | 259 ms | 22148 KB |