[BOJ] 날카로운 눈 - Compy's Blog

날카로운 눈

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 ≤ N ≤ 20000 1 ≤ A, B, C ≤ 2,147,483,647)	Binary Search

솔직히 처음에 엄청 해맸습니다. 문제가 하나만 홀수라는 포인트를 못 읽어서 아주 많이 생각을 해봤는데요. 음.. 문제가 너무 안 풀려서 처음으로 돌아가려니까 그제서야 보이더라구요.

친구는 xor로 열심히 memoization 돌려서 풀더라구요? 엄청 신기하기도 했습니다. 저는 옆에서 binary search 열심히 돌려서 AC 맞았구요.

힘들었던 필기를 소개합니당

그래도 정말 재미있게 풀었던 문제였습니다.

정답 코드

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <random>

#define mod 1000000007LL
//          1000000007
#define M 2147483647

using namespace std;
using ll = long long;
int n;

struct node{
    ll a, c, b;
};

node nodes[20001];


ll count(ll target){
    
    ll result = 0;
    for(int i = 0; i < n; i++){
        if(target >= nodes[i].a) result += (min(nodes[i].c, target) - nodes[i].a) / nodes[i].b + 1;
    }
    
    return result;
}


ll solution(){
    
    ll start = 1, finish = M;
    
    while(start <= finish){
        ll pivot = (start + finish) / 2;
        
        ll pivot_count = count(pivot);
//        cout << "pivot: " << pivot << " count: " << pivot_count << "\n";
        if((pivot_count - count(pivot - 1)) % 2 == 1) return pivot;
        
        if(pivot_count % 2 == 0) start = pivot + 1;
        else finish = pivot - 1;
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    cin >> n;
    for(int i = 0; i < n; i++){
        ll a, c, b;
        cin >> a >> c >> b;
        nodes[i] = {a, c, b};
    }
    
    
    ll result = solution();
    if(result == -1) cout << "NOTHING";
    else cout << result << " " << count(result) - count(result-1);
    
    
    return 0;
}

/*
 6 5 1
 1 6 2 9 8
 7 2 6 9 8
 1 8 3 4 2
 7 4 6 2 3
 9 2 3 6 1
 4 2 9 3 1
 3
 */