제출 #1108882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108882		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);

    int N;
    ll x;

    // Read the number of elements and the target XOR value
    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

        // 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
                break;             // No need to check further subarrays for this k
            }
        }

        if (found) {
            // If a valid subarray is found for this k, update the result
            // Since we're searching for the largest k, move to the higher half
            if (mid > result_k || (mid == result_k && current_i < result_i)) {
                result_k = mid;
                result_i = current_i;
            }
            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 + 1 << " " << result_k + 1;

    return 0;
}

• Subtask 1: 0 / 100