[BOJ] ChatGPT의 역작

ChatGPT의 역작

TimeLimit	MemoryLimit	Condition	TAG
1s	1024MB	(1 ≤ N ≤ 200,000, 1 ≤ L_i, R_i ≤ 10^18)	Parametric Search, Binary Search

문제가 그냥 엄청 어렵게 느껴졌습니다. 처음에는 함수를 분석해서 해보려고 했는데, 들어오는 배열 L, R에 대해서 그냥 엄청 바뀌어버리고 뭔 규칙도 없고 사실상 다른 방법으로 풀어야하는데 범위 때문에 이분탐색을 돌려볼까? 생각을 하게 되었어요. 사실 단조성 자체가 없어서 이게 왜 될까 라는 생각 때문에 코드도 못 짜고 있어서, 일단 짜고 내본다음에 다른 방법 생각하자 해서 작성해서 냈더니? %가 많이 올라가더라구요? 그래서 다행히 풀었습니다.

나중에 아이디어 보니까 뭐 제 코드에서도 그렇게 작성하긴 했지만, 무조건 성립하는 뭔가가 있답니다. 허허 신기하네요…

조금 더 설명을 정확히 해보면, 함수에서 x=0일 때는 무조건 False, x=10^18+1은 무조건 True가 나오기 때문에 그 사이에 값은 무조건 교차할 것이다 생각하고 풀어야하는.. 하튼 디지게 어려웠던 문제였습니다. 발상 자체가 힘들었어요..

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
using namespace std;
using ll = unsigned long long;
//ll MOD = 1'000'000'007;
ll MOD = 1.8446744074E19;

ll N;

ll L[200'001], R[200'001];


bool func(ll x){
    ll value = x;
    for(int i = 0; i < N; i++){
        ll l = L[i];
        ll r = R[i];
        if(l <= x && x <= r) value^=(((x|l)+(x&r)*(l^r)) % MOD);
    }
    return (value >= 0x0123456789ABCDEF);
}

void solution(){
    ll left = 0;
    ll right = 1E18;
    
    bool left_value = func(left);
    bool right_value = func(right);
    
    while(left <= right){
        ll pivot = (left + right) / 2;
        
        bool pivot_value = func(pivot);
        
        if(!pivot_value && func(pivot + 1)){
            cout << pivot;
            return;
        }
        
        
        if(!left_value && pivot_value){
            right = pivot;
            right_value = pivot_value;
        }else if(!pivot_value && right_value){
            left=pivot;
            left_value = pivot_value;
        }else{
            left=pivot+1;
            left_value = func(pivot+1);
        }
    
    }
    
    cout << -1;
    return;
}

int main() {
    
    cin >> N;
    for(int i = 0; i < N; i++) cin >> L[i];
    for(int i = 0; i < N; i++) cin >> R[i];
    
    solution();
    cout << "\n";
    
    return 0;
}