Submission #992290

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > match;
  vector< bool > used;

  Bipartite_Matching(int n)
  {
    graph.resize(n);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  bool dfs(int v)
  {
    used[v] = true;
    for(int i = 0; i < graph[v].size(); i++) {
      int u = graph[v][i], w = match[u];
      if(w == -1 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    match.assign(graph.size(), -1);
    for(int i = 0; i < graph.size(); i++) {
      if(match[i] == -1) {
        used.assign(graph.size(), false);
        ret += dfs(i);
      }
    }
    return (ret);
  }
};

int main()
{
  int N, M;
  int xs[100001] = {};
  cin >> N >> M;

  int ret = 0;
  for(int i = 0; i < N; i++) {
    int X;
    cin >> X;
    X %= M;
    xs[X]++;
  }

  for(int i = 0; i < M; i++) {
    if(i == M - i) continue;
    while(xs[i] > 0 && xs[M - i] > 0) {
      ++ret;
      --xs[i];
      --xs[M - i];
    }
    while(xs[i] - 2 >= 0) {
      xs[i] -= 2;
      ++ret;
    }
  }
  cout << ret << endl;
}

Submission Info

Judge Result