Submission #7505916


Source Code Expand

#include<algorithm>
#include<cassert>
#include<climits>
#include<cmath>
#include<cstring>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << endl

constexpr int IINF = (1 << 30) - 1;
constexpr long long LLINF = 1LL << 61;
constexpr double EPS = 1e-8;

const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
bool chmax(T& a, T b, bool equal = false){
    if(a < b || equal && a == b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T& a, T b, bool equal = false){
    if(b < a || equal && a == b){
        a = b;
        return true;
    }
    return false;
}

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

    int n, m;
    cin >> n >> m;

    vector< vector<int> > v(m);
    rep(i, n){
        int x;
        cin >> x;
        v[x % m].emplace_back(x);
    }
    rep(i, m){
        SORT(v[i]);
    }

    int ans = 0;
    rep(i, m / 2 + 1){
        if(i == 0 || (m % 2 == 0 && i == m / 2)){
            ans += (int)v[i].size() / 2;
        }else{
            int j = (int)v[i].size();
            int k = (int)v[m - i].size();
            ans += min(j, k);
            int cnt = 0;
            if(j < k){
                REP(l, 1, v[m - i].size()){
                    if(v[m - i][l] == v[m - i][l - 1]){
                        ++cnt;
                        ++l;
                    }
                }
                ans += min(cnt, (k - j) / 2);
            }else if(j > k){
                REP(l, 1, v[i].size()){
                    if(v[i][l] == v[i][l - 1]){
                        ++cnt;
                        ++l;
                    }
                }
                ans += min(cnt, (j - k) / 2);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task D - Pair Cards
User mhrb
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2723 Byte
Status AC
Exec Time 20 ms
Memory 5760 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 34
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, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 16 ms 892 KB
01-03.txt AC 15 ms 892 KB
01-04.txt AC 16 ms 896 KB
01-05.txt AC 15 ms 768 KB
01-06.txt AC 15 ms 896 KB
01-07.txt AC 14 ms 768 KB
01-08.txt AC 13 ms 896 KB
01-09.txt AC 14 ms 896 KB
01-10.txt AC 18 ms 2432 KB
01-11.txt AC 20 ms 4608 KB
01-12.txt AC 11 ms 892 KB
01-13.txt AC 12 ms 1916 KB
01-14.txt AC 15 ms 788 KB
01-15.txt AC 15 ms 896 KB
01-16.txt AC 14 ms 1024 KB
01-17.txt AC 13 ms 768 KB
01-18.txt AC 14 ms 1152 KB
01-19.txt AC 16 ms 1280 KB
01-20.txt AC 18 ms 5760 KB
01-21.txt AC 15 ms 896 KB
01-22.txt AC 14 ms 768 KB
01-23.txt AC 13 ms 896 KB
01-24.txt AC 12 ms 896 KB
01-25.txt AC 14 ms 1664 KB
01-26.txt AC 15 ms 3328 KB
01-27.txt AC 10 ms 4224 KB
01-28.txt AC 3 ms 2688 KB
01-29.txt AC 2 ms 1152 KB
01-30.txt AC 3 ms 2560 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB