Submission #13494990


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
using vi = vector<int>;
void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

template<class T>using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;



int main() {
  int N, M;
  ins(N, M);

  vi X(N);
  rep(i, N)
    cin >> X[i];
  all(sort, X);

  vector<int> m(M, 0), p(M, 0);
  map<int, int> count;
  rep(i, N)
    ++count[X[i]];

  vector<priority_queue_rev<int>> group(M);
  vector<int> size(M, 0);
  for (const auto& e : count) {
    group[e.first % M].push(e.second);
    size[e.first % M] += e.second;
  }

  int ans = 0;
  rep(i, M) {
    if (i > (M-i)%M)
      break;
    if (i == 0 || i == (M-i)%M) {
      ans += size[i] / 2;
      continue;
    }
    priority_queue_rev<int> S = group[i], T = group[(M-i)%M];
    if (size[i] <= size[(M-i)%M])
      swap(S, T);

    while (!T.empty()) {
      int p = T.top(); T.pop();
      while (p > 0) {
        if (p >= S.top()) {
          ans += S.top();
          p -= S.top();
          S.pop();
          continue;
        }
        int p2 = S.top()-p;
        ans += p;
        S.pop();
        S.push(p2);
        break;
      }
    }
    while (!S.empty()) {
      int p = S.top(); S.pop();
      ans += p/2;
    }
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Submission Time
Task D - Pair Cards
User pandanoir
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1541 Byte
Status
Exec Time 66 ms
Memory 12800 KB

Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt
all 0 / 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 52 ms 3968 KB
01-03.txt 52 ms 4004 KB
01-04.txt 54 ms 4096 KB
01-05.txt 54 ms 3968 KB
01-06.txt 55 ms 3968 KB
01-07.txt 55 ms 4096 KB
01-08.txt 57 ms 3968 KB
01-09.txt 55 ms 4096 KB
01-10.txt 59 ms 6528 KB
01-11.txt 62 ms 9856 KB
01-12.txt 30 ms 640 KB
01-13.txt 32 ms 2560 KB
01-14.txt 56 ms 5884 KB
01-15.txt 57 ms 6016 KB
01-16.txt 59 ms 6016 KB
01-17.txt 58 ms 5888 KB
01-18.txt 59 ms 6272 KB
01-19.txt 60 ms 6528 KB
01-20.txt 66 ms 12800 KB
01-21.txt 36 ms 896 KB
01-22.txt 38 ms 896 KB
01-23.txt 36 ms 896 KB
01-24.txt 36 ms 896 KB
01-25.txt 37 ms 2176 KB
01-26.txt 40 ms 5248 KB
01-27.txt 33 ms 8704 KB
01-28.txt 6 ms 4864 KB
01-29.txt 3 ms 2048 KB
01-30.txt 4 ms 4608 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB