Submission #993470


Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int> P;
int N, M;
int X[100000];
int v[100000];
vector<P> mod[100000];
int modsum[100000];
int main(){
  cin >> N >> M;
  
  REP(i,N){
    cin >> X[i];
    v[ X[i] ]++;
  }
  REP(i, 100000){
    if( v[i] > 0 ){
      mod[ i % M ].emplace_back( v[i], i );
      modsum[ i % M ] += v[i];
    }
  }
  int ans = 0;
  ans += modsum[0] / 2;
  if( M % 2 == 0 ){
    ans += modsum[ M / 2 ] / 2;
  }
  for(int i = 1; i < M - i; i++ ){
    int j = M - i;
    ans += min( modsum[i] , modsum[j] );
    int d = abs( modsum[i] - modsum[j] );
    if( d == 0 ) continue;
    if( modsum[j] < modsum[i] ){
      // modsum[j] の方が大きくなるようにする
      j = i;
    }
    sort( mod[j].begin(), mod[j].end() );
    reverse( mod[j].begin(), mod[j].end() ); // 個数の多い順番に並べる.
    int e = 0;
    int k = 0;
    bool oddexist = false;
    while( 1 ){
      if( e + mod[j][k].first < d ){
	if( mod[j][k].first % 2 == 1 ) oddexist = true;
	ans += mod[j][k].first / 2;
	e += mod[j][k].first;
      }else{
	ans += (d - e) / 2;
	if( (d - e) % 2 == 1 && oddexist ){
	  ans += 1;
	}
	break;
      }
      k++;
    }
  }
  cout << ans << endl;
}

Submission Info

Submission Time
Task D - Pair Cards
User sndtkrh
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1314 Byte
Status WA
Exec Time 47 ms
Memory 6912 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
WA × 1
AC × 15
WA × 17
Set Name Test Cases
sample sample-01.txt, sample-02.txt
all 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
Case Name Status Exec Time Memory
01-01.txt AC 6 ms 2560 KB
01-02.txt AC 40 ms 3964 KB
01-03.txt WA 40 ms 4048 KB
01-04.txt WA 44 ms 3968 KB
01-05.txt WA 41 ms 3968 KB
01-06.txt WA 42 ms 4096 KB
01-07.txt WA 42 ms 4096 KB
01-08.txt WA 41 ms 3968 KB
01-09.txt WA 42 ms 4224 KB
01-10.txt WA 43 ms 4864 KB
01-11.txt WA 45 ms 5760 KB
01-12.txt AC 39 ms 2944 KB
01-13.txt AC 39 ms 2944 KB
01-14.txt WA 40 ms 4348 KB
01-15.txt WA 40 ms 4296 KB
01-16.txt AC 41 ms 4608 KB
01-17.txt AC 41 ms 4352 KB
01-18.txt AC 42 ms 4864 KB
01-19.txt AC 43 ms 4480 KB
01-20.txt AC 47 ms 6912 KB
01-21.txt AC 38 ms 3456 KB
01-22.txt WA 38 ms 3456 KB
01-23.txt WA 38 ms 3456 KB
01-24.txt WA 39 ms 3456 KB
01-25.txt WA 38 ms 3584 KB
01-26.txt AC 39 ms 3840 KB
01-27.txt AC 26 ms 4736 KB
01-28.txt AC 8 ms 3456 KB
01-29.txt WA 6 ms 3200 KB
01-30.txt AC 6 ms 2688 KB
sample-01.txt AC 6 ms 2560 KB
sample-02.txt WA 6 ms 2560 KB