Submission #1330224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330224		bradley0927	Grid Coloring (JOI25_ho_t1)	C++20	Compilation error	0 ms	0 KiB

Main

#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;
    }
    */
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:18:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   18 |     sort(mp.begin(), mp.end());
      |     ^~~~
      |     short
Main.cpp:19:14: error: 'unique' was not declared in this scope
   19 |     mp.erase(unique(mp.begin(), mp.end()), mp.end()); // unique sorted values
      |              ^~~~~~