Submission #992241

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
vector<set<in> > cc;
map<in,in> cnt;
VI ttc;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,m,x;
  cin>>n>>m;
  cc.resize(m);
  ttc.resize(m);
  forn(z,n){
    cin>>x;
    cc[x%m].insert(x);
    ++ttc[x%m];
    ++cnt[x];
  }
  VI bd={0};
  if(m%2==0)
    bd.PB(m/2);
  in sm=0;
  forv(i,bd){
    sm+=ttc[bd[i]]/2;
  }
  for(in i=1;i<(m-i);++i){
    auto a=cc[i].begin();
    auto b=cc[m-i].begin();
    while(a!=cc[i].end() && b!=cc[m-i].end()){
      if(cnt[*a]%2==0){
	++a;
	continue;
      }
      if(cnt[*b]%2==0){
	++b;
	continue;
      }
      ++sm;
      --cnt[*a];
      --cnt[*b];
    }
    in loa=0;
    in lob=0;
    while(a!=cc[i].end()){
      loa+=cnt[*a]%2;
      ++a;
    }
    while(b!=cc[m-i].end()){
      lob+=cnt[*b]%2;
      ++b;
    }
    in ttla=0;
    in ttlb=0;
    fors(it,cc[i])
      ttla+=(cnt[*it]-cnt[*it]%2);
    fors(it,cc[m-i])
      ttlb+=(cnt[*it]-cnt[*it]%2);
    loa-=loa%2;
    lob-=lob%2;
    in c=min(loa,ttlb);
    ttlb-=c;
    sm+=c;
    c=min(lob,ttla);
    ttla-=c;
    sm+=c;
    sm+=ttla/2;
    sm+=ttlb/2;
  }
  cout<<sm<<endl;
  return 0;
}

Submission Info

Judge Result