Submission #992430


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> X(n); cin >> X;
    map<int, int> cnt, cnt2;
    REP(i, n) {
        cnt[X[i]%m]++;
        cnt2[X[i]]++;
    }
    map<int, int> self;
    EACH(p, cnt2) {
        // cout << p.first << " " << p.second << endl;
        self[p.first%m] += p.second/2;
    }
    set<int> used;
    ll ans = 0;
    EACH(p, cnt) {
        int x, c; tie(x, c) = p;
        if ( used.count(x) > 0 ) continue;
        int y = m-x;
        used.insert(x);
        used.insert(y);
        if (x == y) {
            ans += c/2;
            // cout << c << endl;
        }
        else if (x == m || y == m) {
            ans += (cnt[x]+cnt[y])/2;
        }
        else {
            int c1 = c, c2 = cnt[y];
            int l1 = self[x], l2 = self[y];
            int M = 0;
            REP(i, min(c1, c2)+1) {
                int a = i;
                a += min<int>((c1-i)/2, l1);
                a += min<int>((c2-i)/2, l2);
                M = max(M, a);
            }
            ans += M;
        }
    }
    cout << ans << endl;
}

Submission Info

Submission Time
Task D - Pair Cards
User drafear
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2240 Byte
Status AC
Exec Time 179 ms
Memory 19456 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 39 ms 3584 KB
01-03.txt AC 40 ms 3584 KB
01-04.txt AC 41 ms 3584 KB
01-05.txt AC 41 ms 3584 KB
01-06.txt AC 43 ms 3584 KB
01-07.txt AC 44 ms 3584 KB
01-08.txt AC 50 ms 3712 KB
01-09.txt AC 55 ms 3840 KB
01-10.txt AC 90 ms 9216 KB
01-11.txt AC 131 ms 15744 KB
01-12.txt AC 11 ms 640 KB
01-13.txt AC 11 ms 640 KB
01-14.txt AC 48 ms 5376 KB
01-15.txt AC 49 ms 5376 KB
01-16.txt AC 53 ms 5376 KB
01-17.txt AC 59 ms 5376 KB
01-18.txt AC 70 ms 5760 KB
01-19.txt AC 79 ms 7040 KB
01-20.txt AC 179 ms 19456 KB
01-21.txt AC 20 ms 896 KB
01-22.txt AC 22 ms 896 KB
01-23.txt AC 23 ms 896 KB
01-24.txt AC 28 ms 1024 KB
01-25.txt AC 34 ms 1792 KB
01-26.txt AC 33 ms 1920 KB
01-27.txt AC 132 ms 16896 KB
01-28.txt AC 8 ms 1280 KB
01-29.txt AC 3 ms 512 KB
01-30.txt AC 3 ms 256 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB