| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1330224 | bradley0927 | Grid Coloring (JOI25_ho_t1) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
// -------------------
// Step 1: coordinate compression
// -------------------
vector<int> mp = a;
mp.insert(mp.end(), b.begin(), b.end());
sort(mp.begin(), mp.end());
mp.erase(unique(mp.begin(), mp.end()), mp.end()); // unique sorted values
int k = mp.size();
// map original values to compressed indices
for (int i = 0; i < n; i++) a[i] = lower_bound(mp.begin(), mp.end(), a[i]) - mp.begin();
for (int i = 0; i < n; i++) b[i] = lower_bound(mp.begin(), mp.end(), b[i]) - mp.begin();
// -------------------
// Step 2: frequency arrays
// -------------------
vector<int> fa(k, 0), fb(k, 0);
for (int x : a) fa[x]++;
for (int x : b) fb[x]++;
// -------------------
// Step 3: prefix sums
// -------------------
vector<int> psa(k, 0), psb(k, 0);
psa[0] = fa[0]; psb[0] = fb[0];
for (int i = 1; i < k; i++) {
psa[i] = psa[i-1] + fa[i]; // # of a[i] ≤ current
psb[i] = psb[i-1] + fb[i]; // # of b[j] ≤ current
}
// -------------------
// Step 4: count contributions
// -------------------
vector<int> cnt(k, 0);
int max_cnt = 0, max_idx = 0;
auto comp = [&](int v){
if (cnt[v] > max_cnt) {
max_cnt = cnt[v];
max_idx = v;
} else if (cnt[v] == max_cnt) {
max_idx = max(max_idx, v); // tie-breaker: largest value
}
};
for (int v = 0; v < k; v++) {
// cells where max = v:
// Case 1: a[i] = v, b[j] ≤ v
int c1 = fa[v] * psb[v];
// Case 2: b[j] = v, a[i] < v
int c2 = fb[v] * (psa[v] - fa[v]);
cnt[v] = c1 + c2;
comp(v);
}
// -------------------
// Step 5: output
// -------------------
cout << mp[max_idx] << " " << max_cnt << endl;
// Optional: print counts for all values
/*
cout << "Counts per value:" << endl;
for (int i = 0; i < k; i++) {
cout << mp[i] << ": " << cnt[i] << endl;
}
*/
}