Submission #3225657


Source Code Expand

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

public class Main {
    InputStream is;

    int __t__ = 1;
    int __f__ = 0;
    int __FILE_DEBUG_FLAG__ = __f__;
    String __DEBUG_FILE_NAME__ = "src/D1";

    FastScanner in;
    PrintWriter out;

    int[] imos;
    public void solve() {
        String s = in.next();
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(s.charAt(i) == '1' ? '0' : '1');
        }
        String rs = sb.toString();
        imos = new int[n];

        int lo = 0, hi = n + 1;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            if (isOk(s, mid) || isOk(rs, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        System.out.println(lo);
    }

    private boolean isOk(String s, int l) {
        Arrays.fill(imos, 0);
        int cur = 0;
        for (int i = 0; i + l < s.length(); i++) {
            int next = ((s.charAt(i) - '0') + cur) % 2;
            if (next == 1) {
                imos[i]++;
                imos[i+l-1]--;
            }
            cur += imos[i];
        }
        int zlen = s.length() - l;
        boolean isZero = true;
        for (int i = s.length() - l; i < s.length(); i++) {
            int next = ((s.charAt(i) - '0') + cur) % 2;
            if (isZero) {
                if (next == 0) {
                    zlen++;
                } else {
                    isZero = false;
                }
            } else {
                if (next == 0) {
                    return false;
                }
            }
            cur += imos[i];
        }
        int olen = s.length() - zlen;
        return l <= zlen || l <= olen;
    }



    public void run() {
        if (__FILE_DEBUG_FLAG__ == __t__) {
            try {
                is = new FileInputStream(__DEBUG_FILE_NAME__);
            } catch (FileNotFoundException e) {
                // TODO 自動生成された catch ブロック
                e.printStackTrace();
            }
            System.out.println("FILE_INPUT!");
        } else {
            is = System.in;
        }
        in = new FastScanner(is);
        out = new PrintWriter(System.out);

        solve();
    }

    public static void main(final String[] args) {
        new Main().run();
    }

    class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastScanner(InputStream stream) {
            this.stream = stream;
            // stream = new FileInputStream(new File("dec.in"));

        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        boolean isEndline(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++)
                array[i] = nextInt();

            return array;
        }

        int[][] nextIntMap(int n, int m) {
            int[][] map = new int[n][m];
            for (int i = 0; i < n; i++) {
                map[i] = in.nextIntArray(m);
            }
            return map;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        long[] nextLongArray(int n) {
            long[] array = new long[n];
            for (int i = 0; i < n; i++)
                array[i] = nextLong();

            return array;
        }

        long[][] nextLongMap(int n, int m) {
            long[][] map = new long[n][m];
            for (int i = 0; i < n; i++) {
                map[i] = in.nextLongArray(m);
            }
            return map;
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        double[] nextDoubleArray(int n) {
            double[] array = new double[n];
            for (int i = 0; i < n; i++)
                array[i] = nextDouble();

            return array;
        }

        double[][] nextDoubleMap(int n, int m) {
            double[][] map = new double[n][m];
            for (int i = 0; i < n; i++) {
                map[i] = in.nextDoubleArray(m);
            }
            return map;
        }

        String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        String[] nextStringArray(int n) {
            String[] array = new String[n];
            for (int i = 0; i < n; i++)
                array[i] = next();

            return array;
        }

        String nextLine() {
            int c = read();
            while (isEndline(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndline(c));
            return res.toString();
        }
    }
}

Submission Info

Submission Time
Task D - Wide Flip
User hiro116s
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 6273 Byte
Status WA
Exec Time 143 ms
Memory 25556 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 14
WA × 16
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt WA 141 ms 23380 KB
02.txt WA 141 ms 20176 KB
03.txt WA 139 ms 24276 KB
04.txt WA 143 ms 21972 KB
05.txt WA 139 ms 21716 KB
06.txt WA 138 ms 24276 KB
07.txt WA 131 ms 22228 KB
08.txt WA 134 ms 23508 KB
09.txt WA 141 ms 25556 KB
10.txt WA 137 ms 20948 KB
11.txt WA 143 ms 23764 KB
12.txt WA 132 ms 22608 KB
13.txt WA 137 ms 23764 KB
14.txt WA 140 ms 24276 KB
15.txt WA 139 ms 24276 KB
16.txt WA 138 ms 23508 KB
17.txt AC 131 ms 21716 KB
18.txt AC 131 ms 22612 KB
19.txt AC 135 ms 24148 KB
20.txt AC 132 ms 22484 KB
21.txt AC 69 ms 21076 KB
22.txt AC 69 ms 22996 KB
23.txt AC 68 ms 19924 KB
24.txt AC 69 ms 20564 KB
25.txt AC 68 ms 19540 KB
26.txt AC 67 ms 19412 KB
27.txt AC 68 ms 20180 KB
s1.txt AC 69 ms 19412 KB
s2.txt AC 69 ms 20052 KB
s3.txt AC 69 ms 20308 KB