h_nosonの日記

競プロ、CTFなど

Codeforces Round #350 (Div. 2) C. Cinema

問題
Problem - C - Codeforces
N人の人がいる.それぞれ使える言語A_iは1つだけである.M個の映画があり,音声と字幕は違う言語B_i,C_iが使われている.1つの映画を全員で見るとき最も多くの人が満足できる映画はどれか.
音声に満足している人が等しいならば字幕で比較する.

制約
1\leq N,M\leq20000
1\leq A_i,B_i,C_i\leq10^9

解法
mapを使って使える言語を数え上げ,その値で音声と字幕の組を比較し,最も満足される映画を選ぶ.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

map<int,int> mp;

bool cmp(const pair<int,int>& p, const pair<int,int>& q) {
    if (mp[p.first] == mp[q.first])
        return mp[p.second] < mp[q.second];
    else
        return mp[p.first] < mp[q.first];
}

int main() {
    int i, n, m;
    int a[200000], b[200000], c[200000];
    pair<int,int> p[200000];
    scanf("%d",&n);
    rep (i,n) scanf("%d",a+i);
    scanf("%d",&m);
    rep (i,m) scanf("%d",b+i);
    rep (i,m) scanf("%d",c+i);

    rep (i,n) mp[a[i]]++;
    rep (i,m) {
        p[i].first = b[i];
        p[i].second = c[i];
    }
    auto mx = max_element(p,p+m,cmp);
    rep (i,m) if (b[i] == mx->first && c[i] == mx->second) {
        printf("%d\n",i+1);
        break;
    }
    return 0;
}