logoChat01.ai

import java.io.*; import java.util.*; public class...

Created on: August 10, 2025

Answered using GPT-5 Thinking by Chat01

Question

import java.io.;
import java.util.;
public class Main {
static class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
while ((c = read()) <= 32) if (c == -1) return -1;
int sign = 1;
if (c == '-') { sign = -1; c = read(); }
int val = 0;
while (c > 32) {
val = val * 10 + c - '0';
c = read();
}
return val * sign;
}
String next() throws IOException {
int c;
while ((c = read()) <= 32) if (c == -1) return null;
StringBuilder sb = new StringBuilder();
while (c > 32) {
sb.append((char) c);
c = read();
}
return sb.toString();
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner();
int t = fs.nextInt();
StringBuilder out = new StringBuilder();
while (t-- > 0) {
int n = fs.nextInt();
String a = fs.next();
String b = fs.next();
int[] prefA = new int[n+1];
int[] prefB = new int[n+1];
for (int i = 1; i <= n; i++) prefA[i] = prefA[i-1] + (a.charAt(i-1) == '1' ? 1 : 0);
for (int i = 1; i <= n; i++) prefB[i] = prefB[i-1] + (b.charAt(i-1) == '1' ? 1 : 0);
int[] delta = new int[n];
int[] B0 = new int[n];
int[] B1 = new int[n];
for (int y = 1; y <= n; y++) {
B0[y-1] = prefB[y];
B1[y-1] = y - prefB[y];
delta[y-1] = 2 * prefB[y] - y;
}
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (i,j) -> Integer.compare(delta[i], delta[j]));
long[] prefB0 = new long[n+1];
long[] prefB1 = new long[n+1];
int[] sortedDelta = new int[n];
for (int i = 1; i <= n; i++) {
int id = idx[i-1];
sortedDelta[i-1] = delta[id];
prefB0[i] = prefB0[i-1] + B0[id];
prefB1[i] = prefB1[i-1] + B1[id];
}
long totalB1 = prefB1[n];
long ans = 0;
for (int x = 1; x <= n; x++) {
int A0 = prefA[x];
int A1 = x - A0;
int Dx = 2 * A0 - x;
int T = -Dx;
int lo = 0, hi = n - 1, pos = -1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (sortedDelta[mid] <= T) {
pos = mid;
lo = mid + 1;
} else hi = mid - 1;
}
int k = pos + 1;
long sum1 = (long)k * A0 + prefB0[k];
long sum2 = (long)(n - k) * A1 + (totalB1 - prefB1[k]);
ans += sum1 + sum2;
}
out.append(ans).append('\n');
}
System.out.print(out.toString());
}
}
simplify the code

Thought

Simplifying code logic

Let's simplify the Java algorithm by refactoring it with clearer variable names and combining unnecessary loops. I'll avoid using arrays when possible, add comments for clarity, and potentially integrate streams for conciseness. We need to keep the algorithm's behavior the same but streamline its structure, especially for competitive programming while using FastScanner.

Refining algorithm steps

Now, for each x from 1 to n, I calculate A0, A1, Dx, and T. I perform binary search to find the count of y with delta <= T, then compute sum1 and sum2 using these counts. I realize A0 should be renamed to onesA, and A1 to zerosA for better readability. The sum computations could be simplified further, but they seem to handle total matches.

Simplifying and optimizing

I see opportunities to simplify the code. First, instead of arrays B0 and B1, I can compute them from prefB during the sorted array construction. Using a custom Node class for delta, B0, and B1 paired together will help with sorting. Binary search can be streamlined with a helper function for the upper bound. I’ll also improve variable names and comments, unifying prefA calculations. Finally, I’ll stick with FastScanner, as it's efficient enough, and ensure the answer uses long for edge cases.

Simplifying code structure

To simplify the code, I’ll refactor the loops to compute prefix sums directly from character values rather than using arrays. For building the prefix sums for a and b, I’ll use integer arrays and update them in a single pass. I'll craft helper functions and make sure to handle arrays efficiently with proper sorting and deltas.

Thought for 22s

Answer

Here’s a cleaner, shorter version with clearer names, one binary-search helper, and fewer temporary arrays—same logic and complexity (O(n log n)):

java
import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0, len = 0;
        private int read() throws IOException {
            if (ptr >= len) { len = in.read(buf); ptr = 0; if (len <= 0) return -1; }
            return buf[ptr++];
        }
        int nextInt() throws IOException {
            int c; while ((c = read()) <= 32) if (c == -1) return -1;
            int sign = 1; if (c == '-') { sign = -1; c = read(); }
            int v = 0; while (c > 32) { v = v * 10 + (c - '0'); c = read(); }
            return v * sign;
        }
        String next() throws IOException {
            int c; while ((c = read()) <= 32) if (c == -1) return null;
            StringBuilder sb = new StringBuilder();
            while (c > 32) { sb.append((char) c); c = read(); }
            return sb.toString();
        }
    }

    static class Node {
        int delta;   // ones - zeros in B prefix
        int bOnes;   // ones in B prefix
        int bZeros;  // zeros in B prefix
        Node(int delta, int bOnes, int bZeros) { this.delta = delta; this.bOnes = bOnes; this.bZeros = bZeros; }
    }

    // returns last index with a[i] <= target (upper bound - 1), or -1 if none
    static int upperBound(int[] a, int target) {
        int lo = 0, hi = a.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int t = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (t-- > 0) {
            int n = fs.nextInt();
            String a = fs.next();
            String b = fs.next();

            // prefix ones counts for A and B
            int[] pa = new int[n + 1], pb = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                pa[i] = pa[i - 1] + (a.charAt(i - 1) - '0');
                pb[i] = pb[i - 1] + (b.charAt(i - 1) - '0');
            }

            // Build nodes for each B prefix, then sort by delta
            Node[] nodes = new Node[n];
            for (int y = 1; y <= n; y++) {
                int ones = pb[y];
                int zeros = y - ones;
                nodes[y - 1] = new Node(ones - zeros, ones, zeros); // delta = 2*ones - y
            }
            Arrays.sort(nodes, Comparator.comparingInt(nd -> nd.delta));

            // Prepare arrays for binary search and prefix sums over sorted B prefixes
            int[] deltas = new int[n];
            long[] prefOnesB = new long[n + 1];
            long[] prefZerosB = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                Node nd = nodes[i - 1];
                deltas[i - 1] = nd.delta;
                prefOnesB[i] = prefOnesB[i - 1] + nd.bOnes;
                prefZerosB[i] = prefZerosB[i - 1] + nd.bZeros;
            }
            long totalZerosB = prefZerosB[n];

            long ans = 0;
            for (int x = 1; x <= n; x++) {
                int onesA = pa[x];
                int zerosA = x - onesA;
                int deltaA = onesA - zerosA;  // 2*onesA - x
                int threshold = -deltaA;

                int k = upperBound(deltas, threshold) + 1; // # of B prefixes with delta <= threshold

                long sum1 = (long) k * onesA + prefOnesB[k];
                long sum2 = (long) (n - k) * zerosA + (totalZerosB - prefZerosB[k]);
                ans += sum1 + sum2;
            }

            out.append(ans).append('\n');
        }

        System.out.print(out.toString());
    }
}

Key changes: clearer names, a small Node to avoid parallel arrays + index indirection, a reusable upperBound, and comments so the flow is easy to follow.

Share this Q&A