제출 #1108946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108946		nitro007	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	336 KiB

xor

#include <bits/stdc++.h>
using namespace std;

// Define a type alias for long long for convenience
typedef long long ll;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    ll N, x;
    cin >> N >> x;

    vector<ll> A(N);

    // Read the array elements
    for (int i = 0; i < N; ++i)
        cin >> A[i];

    // Compute the prefix XOR array
    // prefix_xor[i] = A[0] ^ A[1] ^ ... ^ A[i-1]
    // prefix_xor[0] = 0 (XOR of zero elements)
    vector<ll> prefix_xor(N + 1, 0);
    for (int i = 1; i <= N; ++i)
        prefix_xor[i] = prefix_xor[i - 1] ^ A[i - 1];

    // Initialize binary search boundaries
    int low = 1;          // Minimum possible k
    int high = N;         // Maximum possible k
    int result_k = 0;    // To store the maximum k found
    int result_i = 0;    // To store the smallest i for the maximum k

    // Binary search to find the maximum k
    while (low <= high) {
        int mid = low + (high - low) / 2; // Avoid potential overflow

        bool found = false;      // Flag to indicate if any subarray of length mid satisfies the condition
        int current_i = -1;      // To store the starting index of the first valid subarray found
        int current_k = -1;
        // Iterate through all possible subarrays of length mid
        for (int l = 0; l + mid <= N; ++l) {
            // Compute XOR of subarray [l, l+mid-1] using prefix XOR
            ll subarray_xor = prefix_xor[l + mid] ^ prefix_xor[l];

            if (subarray_xor >= x) {
                // Valid subarray found
                found = true;
                current_i = l + 1; // Convert to 1-based index
                current_k = l + mid;
                break;             // No need to check further subarrays for this k
            }
        }

        if (found) {
            result_i = current_i;
            result_k = current_k-current_i + 1;
            low = mid + 1;
        }
        else {
            // If no valid subarray is found for this k, search in the lower half
            high = mid - 1;
        }
    }

    // After binary search, result_k holds the maximum k, and result_i holds the smallest i
    cout << result_i << " " << result_k;

    return 0;
}

• Subtask 1: 0 / 100