Submission #992266

---

Source Code Expand

/* -------------------------------- Template -------------------------------- */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }

template<typename T> constexpr T inf = [](){ assert(false); };
// template<> constexpr int inf<int> = 1e9;
// template<> constexpr ll inf<ll> = 1e18;
// template<> constexpr ld inf<ld> = 1e30;

struct yes_no : std::numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve();

int main() {
  std::locale loc(std::locale(), new yes_no);
  std::cout << std::boolalpha << std::setprecision(12) << std::fixed;
  std::cout.imbue(loc);
  solve();
  return 0;
}

using namespace std;

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

void solve() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> vec(M);
  REP(i,N) {
    int X; cin >> X;
    vec[X % M].push_back(X);
  }
  REP(i,M) sort(ALL(vec[i]));
  vector<int> one(M), two(M);
  REP(i,M) {
    const int n = vec[i].size();
    REP(j,n) {
      if (j < n - 1 && vec[i][j] == vec[i][j+1]) {
        ++j;
        ++two[i];
      }
      else ++one[i];
    }
  }
  int res = 0;
  REP(i,(M+2)/2) {
    if (i * 2 == M) {
      res += two[i] + one[i] / 2;
    }
    else if (i == 0) {
      res += two[i] + one[i] / 2;
    }
    else {
      const int a = min(one[i], one[M-i]);
      one[i] -= a; one[M-i] -= a; res += a;
      const int b = min(one[i], two[M-i] * 2);
      one[i] -= b; two[M-i] -= (b+1)/2; res += b;
      const int c = min(two[i] * 2, one[M-i]);
      two[i] -= (c+1)/2; one[M-i] -= c; res += c;
      res += two[i] + two[M-i];
    }
    // cout << res << endl;
  }
  cout << res << endl;
  return;
}

Submission Info

Judge Result