Codeforces 2254C2 — Marenol (Hard Version)

Key Idea

In both operations, a 1 moves exactly 2 positions.

So the parity of every 1 is preserved:

• even → even
• odd → odd

Store the positions of 1s separately for even and odd indices in both strings.

If the counts don't match for either parity, answer is -1.

Otherwise, match the 1s in order. Moving from position x to y takes:

|x - y| / 2

Complexity

O(n) time and O(n) space.

Java 21

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

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

            ArrayList<Integer>[] x = new ArrayList[2];
            ArrayList<Integer>[] y = new ArrayList[2];

            for (int i = 0; i < 2; i++) {
                x[i] = new ArrayList<>();
                y[i] = new ArrayList<>();
            }

            for (int i = 0; i < n; i++) {
                if (a.charAt(i) == '1') x[i % 2].add(i);
                if (b.charAt(i) == '1') y[i % 2].add(i);
            }

            long ans = 0;
            boolean ok = true;

            for (int p = 0; p < 2; p++) {
                if (x[p].size() != y[p].size()) {
                    ok = false;
                    break;
                }

                for (int i = 0; i < x[p].size(); i++)
                    ans += Math.abs(x[p].get(i) - y[p].get(i)) / 2;
            }

            System.out.println(ok ? ans : -1);
        }
    }
}