Submission #994964


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <numeric>
#include <deque>
#include <limits>
#include <set>
#include <map>

using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) // cerr << __LINE__ << ":\t" #x " = " << x << endl


int n, m;
vector<int> x;
map<int, int> cnt;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while (cin >> n >> m) {
        cnt.clear();
        x.resize(n);
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            x[i] = a;
            ++cnt[a];
        }
        vector<vector<int>> v(m);
        for (auto &p : cnt) {
            v[p.first % m].push_back(p.second);
        }

        int ans = 0;

        for (int i = 0; i <= m / 2; i++) {
            dump(i);
            if (i == 0 || i == m - i) {
                int add = accumulate(v[i].begin(), v[i].end(), 0) / 2;
                dump(add);
                ans += add;
            } else {
                auto &p = v[i], &q = v[m - i];
                int sp = accumulate(all(p), 0);
                int sq = accumulate(all(q), 0);
                auto &many = sp > sq ? p : q;
                int diff = abs(sp - sq);
                for (auto &x : many) {
                    while (diff >= 1 && x >= 2) {
                        int add = 1;
                        diff -= 2;
                        x -= 2;
                        dump(add);
                        ans += add;
                    }
                }

                int rem_p = 0, rem_q = 0;
                for (auto &x : p) {
                    rem_p += x;
                }
                for (auto &x : q) {
                    rem_q += x;
                }
                int add = min(rem_p, rem_q);
                dump(add);
                ans += add;
            }
        }

        //for (auto &sz : v) {
        //    for (int x : sz) {
        //        ans += x / 2;
        //    }
        //}
            cout << ans << endl;
    }
}

Submission Info

Submission Time
Task D - Pair Cards
User tubo28
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2221 Byte
Status AC
Exec Time 57 ms
Memory 10752 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 3 ms 256 KB
01-02.txt AC 40 ms 3968 KB
01-03.txt AC 40 ms 4004 KB
01-04.txt AC 40 ms 4096 KB
01-05.txt AC 40 ms 3968 KB
01-06.txt AC 40 ms 3968 KB
01-07.txt AC 40 ms 4096 KB
01-08.txt AC 41 ms 3968 KB
01-09.txt AC 41 ms 4096 KB
01-10.txt AC 45 ms 5632 KB
01-11.txt AC 48 ms 7936 KB
01-12.txt AC 11 ms 640 KB
01-13.txt AC 12 ms 1664 KB
01-14.txt AC 48 ms 6012 KB
01-15.txt AC 49 ms 6016 KB
01-16.txt AC 49 ms 6016 KB
01-17.txt AC 49 ms 5888 KB
01-18.txt AC 49 ms 6272 KB
01-19.txt AC 51 ms 6272 KB
01-20.txt AC 57 ms 10752 KB
01-21.txt AC 19 ms 896 KB
01-22.txt AC 19 ms 896 KB
01-23.txt AC 19 ms 896 KB
01-24.txt AC 20 ms 896 KB
01-25.txt AC 21 ms 1664 KB
01-26.txt AC 23 ms 3328 KB
01-27.txt AC 30 ms 6656 KB
01-28.txt AC 7 ms 2816 KB
01-29.txt AC 4 ms 1280 KB
01-30.txt AC 6 ms 2560 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB