제출 #1108927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108927		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 = 1;    // To store the maximum k found
    int result_i = 1;    // 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 << " " << result_k;
    
    return 0;
}

• Subtask 1: 0 / 100