Submission #74771727

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Participant {
    int id;
    int priority;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<Participant> p(N);
    for (int i = 0; i < N; ++i) {
        p[i].id = i + 1;
        cin >> p[i].priority;
    }

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Sort neighbors to pick the smallest ID first
    for (int i = 1; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }

    // Sort participants by priority descending
    sort(p.begin(), p.end(), [](const Participant& a, const Participant& b) {
        return a.priority > b.priority;
    });

    vector<bool> is_paired(N + 1, false);
    vector<int> partner(N + 1, 0);
    vector<int> head(N + 1, 0); // Pointer to next available candidate

    for (int i = 0; i < N; ++i) {
        int x = p[i].id;
        if (is_paired[x]) continue;

        // Find the smallest ID available partner
        while (head[x] < adj[x].size()) {
            int y = adj[x][head[x]];
            if (!is_paired[y]) {
                is_paired[x] = true;
                is_paired[y] = true;
                partner[x] = y;
                partner[y] = x;
                break;
            }
            head[x]++;
        }
    }

    // Output Aoki's (participant 1) partner
    cout << partner[1] << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:52:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while (head[x] < adj[x].size()) {

Judge Result