문제가 그냥 엄청 어렵게 느껴졌습니다. 처음에는 함수를 분석해서 해보려고 했는데, 들어오는 배열 L, R에 대해서 그냥 엄청 바뀌어버리고 뭔 규칙도 없고
사실상 다른 방법으로 풀어야하는데 범위 때문에 이분탐색을 돌려볼까? 생각을 하게 되었어요. 사실 단조성 자체가 없어서 이게 왜 될까 라는 생각 때문에 코드도 못 짜고 있어서,
일단 짜고 내본다음에 다른 방법 생각하자 해서 작성해서 냈더니? %가 많이 올라가더라구요? 그래서 다행히 풀었습니다.
나중에 아이디어 보니까 뭐 제 코드에서도 그렇게 작성하긴 했지만, 무조건 성립하는 뭔가가 있답니다.
허허 신기하네요…
조금 더 설명을 정확히 해보면, 함수에서 x=0일 때는 무조건 False, x=10^18+1은 무조건 True가 나오기 때문에
그 사이에 값은 무조건 교차할 것이다 생각하고 풀어야하는..
하튼 디지게 어려웠던 문제였습니다. 발상 자체가 힘들었어요..
정답 코드 CPP</>
#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;}
compy.log