Submission #993633


Source Code Expand

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define MAX 100010
int N,M,X[MAX],used_counter[MAX], mod_counter[MAX];
set<int> freq_set[MAX];

// TODO :: 1 のときバグらないかチェック
void compute() {
  map<int,int> freq;

  rep(i,N) {
    ++mod_counter[X[i]%M];
    freq_set[X[i]%M].insert(X[i]);
    ++freq[X[i]];
  }
  map<int,bool> is_odd;
  rep(i,N) {
    if( freq[X[i]] % 2 == 1 ) is_odd[X[i]] = true;
    else                      is_odd[X[i]] = false;
  }

  int answer = 0;
  rep(i,(int)(M/2)+1) {
    if( i == 0 ) {
      int use = (int)(mod_counter[i]/2);
      answer += use;
      used_counter[i] += use;
      continue;
    }
    int half = M - i;
    if( half == i ) {
      int use = (int)(mod_counter[i]/2);
      used_counter[half] += ( use * 2 );
      answer             += use;
      // cout << half << " :MID: use = " << use <<  "| answer = " << answer<< endl;
    } else {
      int use = min(mod_counter[half],mod_counter[i]);
      used_counter[half] += use;
      used_counter[i]    += use;
      answer             += use;
      /*
      cout << "mod_counter[" << half << "] = " << mod_counter[half] << endl;
      cout << "mod_counter[" << i << "] = " << mod_counter[i] << endl;
      cout << half << " :half: use = " << use << endl;
      cout << i    << " :i   : use = " << use << " | answer = " << answer<< endl;
      */
    }
    //puts("");
  }
  //cout << "中間発表 :: " << answer << endl;
  REP(i,1,M) {
    int remain = used_counter[i];
    for(set<int>::iterator it=freq_set[i].begin();it!=freq_set[i].end();++it) {
      if( remain <= 0 ) break;
      int v = *it;
      if( is_odd[v] ) {
	--remain;
	--freq[v];
	assert( freq[v] >= 0 );
      }
    }  
    for(set<int>::iterator it=freq_set[i].begin();it!=freq_set[i].end();++it) {
      int v = *it;
      int cnt = freq[v];
      if( remain ) {
	assert( cnt % 2 == 0 );
	int sub = min(remain,cnt);
	cnt    -= sub;
	remain -= sub;
      }
      assert( cnt >= 0 );
      answer += (int)(cnt/2);
    }
    assert(remain == 0);
  }
  cout << answer << endl;
}

int bf() {
  vector<int> vec;
  rep(i,N) vec.push_back(X[i]);
  sort(vec.begin(),vec.end());
  int maxi = 0;
  do {
    int cnt = 0;
    for(int i=0;i<N;i+=2) {
      if( i+1 <(int)N && ( (vec[i]+vec[i+1]) % M == 0 || vec[i] == vec[i+1] ) ) {
	++cnt;
      }
    }
    /*
    rep(i,N) {
      cout << vec[i] << ",";
    } puts("");
    */
    maxi = max(maxi,cnt);
  } while( next_permutation(vec.begin(),vec.end()) );
  return maxi;
}

int main(){
  srand((unsigned int)time(NULL));
  /*
  N = 8;
  cout << N << " " << ( M = 4 ) << endl;
  rep(i,N) {
    if( i ) cout << " ";
    cout << rand() % 10 +1;
  } puts(""); return 0;
  */
  
  cin >> N >> M;
  rep(i,N) cin >> X[i];
  //cout << "Answer = " << bf() << endl;
  compute();

  return 0;
}

Submission Info

Submission Time
Task D - Pair Cards
User ChiyomiAnzai
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3005 Byte
Status AC
Exec Time 249 ms
Memory 20224 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 32
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 7 ms 4992 KB
01-02.txt AC 141 ms 14208 KB
01-03.txt AC 155 ms 14208 KB
01-04.txt AC 163 ms 14208 KB
01-05.txt AC 165 ms 14208 KB
01-06.txt AC 181 ms 14208 KB
01-07.txt AC 182 ms 14208 KB
01-08.txt AC 177 ms 14208 KB
01-09.txt AC 173 ms 14208 KB
01-10.txt AC 144 ms 14592 KB
01-11.txt AC 154 ms 14976 KB
01-12.txt AC 37 ms 5504 KB
01-13.txt AC 37 ms 5504 KB
01-14.txt AC 198 ms 19456 KB
01-15.txt AC 205 ms 19328 KB
01-16.txt AC 238 ms 19328 KB
01-17.txt AC 243 ms 19456 KB
01-18.txt AC 249 ms 19456 KB
01-19.txt AC 207 ms 19456 KB
01-20.txt AC 183 ms 20224 KB
01-21.txt AC 76 ms 5888 KB
01-22.txt AC 77 ms 5888 KB
01-23.txt AC 75 ms 5888 KB
01-24.txt AC 71 ms 5888 KB
01-25.txt AC 67 ms 6144 KB
01-26.txt AC 69 ms 6656 KB
01-27.txt AC 81 ms 12800 KB
01-28.txt AC 12 ms 6144 KB
01-29.txt AC 8 ms 5376 KB
01-30.txt AC 8 ms 5376 KB
sample-01.txt AC 7 ms 4992 KB
sample-02.txt AC 7 ms 4992 KB