[백준] 28449번 : 누가 이길까 (C++)

28449번 : 누가 이길까

---

문제)

HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 N명 ARC팀엔 M명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 N × M개의 대결로 이루어진다. 모든 참가자는 코딩실력을 가지고 있다. 대결을 하면 더 높은 코딩실력을 가진 참가자가 승리하고, 두 참가자의 코딩실력이 같다면 무승부가 된다.

하얔이는 이 대회의 결과를 빨리 알고싶어졌다. 하얔이를 위해 대회의 결과를 예측해보자!

 

 

 

 

입력 :

첫째 줄에 HI팀의 인원 수 N, ARC팀의 인원 수 M이 공백으로 구분되어 정수로 주어진다. (1≤ N , M ≤100000)

둘째 줄에 HI팀의 참가자의 코딩실력을 나타내는 길이 N 수열 a_i가 공백으로 구분되어 정수로 주어진다. (1≤ a_i ≤100000)

셋째 줄에 ARC팀의 참가자의 코딩실력을 나타내는 길이 M 수열 b_i가 공백으로 구분되어 정수로 주어진다. (1≤b_i ≤100000)

 

 

 

출력 :

첫째 줄에 HI팀 참가자의 승리 횟수, ARC팀 참가자의 승리 횟수, 무승부 횟수를 공백으로 구분하여 출력한다.

 

 

 

 

 

풀이)

 

// 28449. 누가 이길까
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    vector<int> hi(n);
    vector<int> arc(m);
 
    for (int& ele : hi) cin >> ele;
    for (int& ele : arc) cin >> ele;
 
    sort(hi.begin(), hi.end());
    sort(arc.begin(), arc.end());
 
 
    long long hi_win = 0;
    long long draw = 0;
    long long arc_win = 0;
 
    for (int i = 0; i < n; i++)
    {
        int s = 0;
        int e = m - 1;
 
        // 해당 타겟을 기준으로 무승부인 지점을 찾는다.
        int target = hi[i];
 
        int left_idx = m;
 
        while (s <= e)
        {
            int mid = (s + e) / 2;
 
            if (arc[mid] >= target)
            {
                left_idx = mid;
                e = mid - 1;
            }
            else s = mid + 1;
        }
 
 
        int right_idx = -1;
 
        s = 0;
        e = m - 1;
 
        while (s <= e)
        {
            int mid = (s + e) / 2;
            
            if (arc[mid] <= target)
            {
                right_idx = mid;
                s = mid + 1;
            }
            else e = mid - 1;
        }
 
        hi_win += left_idx;
        draw += (right_idx - left_idx + 1);
        arc_win += (m - right_idx - 1);
    }
 
    cout << hi_win << " " << arc_win << " " << draw;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/28449 

28449번: 누가 이길까