Submission #13473988


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll MOD2=998244353;
const double PI=acos(-1);
const ll INF=1e18;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll n,m;
  cin >> n >> m;
  vl x(n),K(m),M(m,0);
  rep(i,n){
    cin >> x[i];
    K[x[i]%m]++;
  }
  sort(x.begin(),x.end());
  ll cnt=1;
  rep(i,n-1){
    if(x[i]==x[i+1]){
      cnt++;
    }
    else{
      M[x[i]%m]+=cnt/2;
      cnt=1;
    }
  }
  M[x[n-1]%m]+=cnt/2;
  ll ans=0;
  rep(i,m){
    if(i!=0&&2*i!=m){
    ll z=min(K[i],K[(m-i)%m]);
    ans+=z;
    M[i]=min(M[i],K[i]-z);
    K[i]-=z;
    K[(m-i)%m]-=z;
    }
    if(i==0||2*i==m){
      ans+=K[i]/2;
      K[i]-=(K[i]/2)*2;
    }
  }
  rep(i,m){
    M[i]=min(M[i],K[i]/2);
  }
  rep(i,m){
    if(M[i]>=1){
      ans+=M[i];
    }
  }
  cout << ans << endl;
}

Submission Info

Submission Time
Task D - Pair Cards
User NNMochi
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1104 Byte
Status
Exec Time 42 ms
Memory 2560 KB

Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt
all 700 / 700 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt 1 ms 256 KB
01-02.txt 37 ms 1024 KB
01-03.txt 37 ms 1024 KB
01-04.txt 37 ms 1024 KB
01-05.txt 37 ms 1024 KB
01-06.txt 37 ms 1024 KB
01-07.txt 37 ms 1024 KB
01-08.txt 37 ms 1024 KB
01-09.txt 37 ms 1024 KB
01-10.txt 39 ms 1664 KB
01-11.txt 42 ms 2560 KB
01-12.txt 31 ms 1024 KB
01-13.txt 33 ms 1664 KB
01-14.txt 37 ms 1024 KB
01-15.txt 37 ms 1024 KB
01-16.txt 37 ms 1024 KB
01-17.txt 37 ms 1024 KB
01-18.txt 37 ms 1024 KB
01-19.txt 37 ms 1280 KB
01-20.txt 41 ms 2560 KB
01-21.txt 35 ms 1024 KB
01-22.txt 36 ms 1024 KB
01-23.txt 35 ms 1024 KB
01-24.txt 35 ms 1024 KB
01-25.txt 36 ms 1536 KB
01-26.txt 39 ms 2560 KB
01-27.txt 22 ms 2176 KB
01-28.txt 6 ms 1792 KB
01-29.txt 3 ms 896 KB
01-30.txt 5 ms 1792 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB