문제 설명

주厨 Marin은 n개의 고추를 가지고 요리를 만들 예정이다.

그는 나이가 x일 이하인 모든 고추로 요리 A를 만들고, 나머지 모든 고추로 요리 B를 만든다.

각 고추는 자신의 꿈을 가지고 있으며, 자신이 요리 A가 되고 싶은지 요리 B가 되고 싶은지 알고 있다.

하지만 고추들은 x의 값을 모른다. 꿈을 실현하는 고추의 수를 최대화하기 위해 다음과 같은 교환 전략을 수행한다:

• 첫 번째 고추와 두 번째 고추를 비교하고, 두 번째와 세 번째를 비교하는 식으로 진행한다. 마지막으로 (n-1)번째 고추와 n번째 고추를 비교한다.
• 현재 비교 중인 두 고추의 번호를 i, j(i < j)라고 하고, 나이가 더 많은 고추가 요리 A가 되고 싶고, 나이가 더 적은 고추가 요리 B가 되고 싶다면, 그들은 나이를 교환한다.

위와 같은 操作 후 꿈을 실현한 고추의 수를 구하시오.

입력 형식

첫째 줄에 두 정수 n, x가 주어진다.

다음 n개 줄에 각 고추의 나이 aᵢ와 꿈 bᵢ가 주어진다.

• bᵢ = 1이면 i번째 고추가 요리 A가 되고 싶다.
• bᵢ = 0이면 i번째 고추가 요리 B가 되고 싶다.

문제 설명에서 교환 조건의 더严谨한 표현은 다음과 같다:

두 고추 i, j(i < j)가 나이를 교환하는 것은 오직 다음 조건이 모두 만족될 때이다: aᵢ > aⱼ 且 bᵢ = 1 且 bⱼ = 0

출력 형식

꿈을 실현한 고추의 수를 하나의 정수로 출력한다.

입출력 예시

예제 입력 1

4 5
2 0
3 0
4 0
5 0

예제 출력 1

0

예제 입력 2

5 5
3 1
2 0
13 1
2 0
10 1

예제 출력 2

5

예제 입력 3

6 10
15 1
12 1
8 0
10 1
3 0
1 1

예제 출력 3

4

Solution

이 문제는 인접한 고추들 사이의 교환을 시뮬레이션하면서 최종적으로 꿈을 실현한 고추의 수를 세는 것이다. 핵심적인 관찰은 다음과 같다:

• 단일 고추가 바로 꿈을 실현할 수 있는 경우: 나이가 x 이하이고 요리 A를 원하거나, 나이가 x 초과이고 요리 B를 원하면 된다.
• 인접한 두 고추가 서로 교환으로 꿈을 실현할 수 있는 경우: 하나의 고추가 나이가 x 초과이고 요리 A를 원하고, 다른 하나의 고추가 나이가 x 이하이고 요리 B를 원할 때.

각 고추가 한 번만 카운트되도록 하기 위해 만족 여부를 추적한다.

#include <bits/stdc++.h>
using namespace std;

struct Pepper {
    int age;
    int dream;
    bool satisfied;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, threshold;
    if (!(cin >> n >> threshold)) return 0;
    
    vector<Pepper> peppers(n);
    for (int i = 0; i < n; i++) {
        cin >> peppers[i].age >> peppers[i].dream;
        peppers[i].satisfied = false;
    }
    
    int answer = 0;
    
    for (int i = 0; i < n - 1; i++) {
        // Check if current pepper already satisfied
        if (!peppers[i].satisfied) {
            // Pepper wants A and age is within limit
            if (peppers[i].dream == 1 && peppers[i].age <= threshold) {
                answer++;
                peppers[i].satisfied = true;
            }
            // Pepper wants B and age exceeds limit
            else if (peppers[i].dream == 0 && peppers[i].age > threshold) {
                answer++;
                peppers[i].satisfied = true;
            }
        }
        
        // Check adjacent pair swap possibility
        if (!peppers[i].satisfied && !peppers[i+1].satisfied) {
            // Case: current wants A with high age, next wants B with low age
            if (peppers[i].dream == 1 && peppers[i].age > threshold &&
                peppers[i+1].dream == 0 && peppers[i+1].age <= threshold) {
                answer += 2;
                peppers[i].satisfied = true;
                peppers[i+1].satisfied = true;
            }
            // Case: current wants B with low age, next wants A with high age
            else if (peppers[i].dream == 0 && peppers[i].age <= threshold &&
                     peppers[i+1].dream == 1 && peppers[i+1].age > threshold) {
                answer += 2;
                peppers[i].satisfied = true;
                peppers[i+1].satisfied = true;
            }
        }
    }
    
    // Handle last pepper
    if (!peppers[n-1].satisfied) {
        if (peppers[n-1].dream == 1 && peppers[n-1].age <= threshold) {
            answer++;
            peppers[n-1].satisfied = true;
        }
        else if (peppers[n-1].dream == 0 && peppers[n-1].age > threshold) {
            answer++;
            peppers[n-1].satisfied = true;
        }
    }
    
    cout << answer << '\n';
    return 0;
}

이 알고리즘은 O(n) 시간 복잡도를 가지며, 각 고추를 한 번씩만 처리한다. 고추가 이미 만족 상태로 표시되어 있으면 중복 카운트를 방지한다.