Submission #992278

---

Source Code Expand

#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve();
void precalc();
clock_t start;
//int timer = 1;

int testNumber = 1;

bool todo = true;

int main() {
#ifdef AIM
    freopen("/home/alexandero/ClionProjects/ACM/input.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
    cout.sync_with_stdio(0);
    cin.tie(0);
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cerr << testNum << endl;
        //cout << "Case #" << testNum++ << ": ";
        solve();
        ++testNumber;
        //++timer;
    }

#ifdef AIM
    cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

    return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

void precalc() {

}

//#define int li

//const int mod = 1000000007;

vector<int> dsu;

void init(int n) {
    dsu.resize(n);
    for (int  i= 0; i < n; ++i) {
        dsu[i] = i;
    }
}

int find_set(int v) {
    if (dsu[v] == v) {
        return v;
    }
    return dsu[v] = find_set(dsu[v]);
}

void merge(int q, int w) {
    q = find_set(q);
    w = find_set(w);
    dsu[w] = q;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> cards(m);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cards[x % m].push_back(x);
    }
    vector<int> sum(m), odd(m);
    for (int i = 0; i < m; ++i) {
        sum[i] = cards[i].size();
        sort(all(cards[i]));
        for (int j = 0; j < cards[i].size(); ) {
            int r = j;
            while (r < cards[i].size() && cards[i][j] == cards[i][r]) {
                ++r;
            }
            int cnt = r - j;
            if (cnt & 1) {
                ++odd[i];
            }
            j = r;
        }
    }

    int dp = 0;
    for (int i = 1; i < (m + 1) / 2; ++i) {
        int j = m - i;
        int new_dp = -1;
        for (int x = 0; x <= sum[i] && x <= sum[j]; ++x) {
            int even_i;
            if (x <= odd[i]) {
                even_i = sum[i] - odd[i];
            }
            else {
                even_i = sum[i] - x;
            }
            int even_j;
            if (x <= odd[j]) {
                even_j = sum[j] - odd[j];
            }
            else {
                even_j = sum[j] - x;
            }
            new_dp = max(new_dp, dp + x + even_i / 2 + even_j / 2);
            //cout << i << ' ' << j << ' ' << even_i << ' ' << even_j << ' ' << x << "\n";
        }
        //cout << new_dp << "\n";
        dp = new_dp;
    }

    dp += sum[0] / 2;
    if (m % 2 == 0) {
        dp += sum[m / 2] / 2;
    }

    cout << dp << "\n";

}

Submission Info

Judge Result