Submission #992907


Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int MOD = 1000000007;

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);

    int n,m;
    cin >> n >> m;
    VI x(n);
    REP(i,n){
        cin >> x[i];
    }

    int maxx = *max_element(ALL(x));
    VI xl(maxx+1,0);
    VI xm(m,0);
    VI xmp(m,0);
    VI xml(m,0);
    REP(i,n){
        xl[x[i]]++;
        xm[x[i]%m]++;
    }

    FOR(i,1,maxx+1){
        xmp[i%m] += xl[i]/2;
        xml[i%m] += xl[i]%2;
    }

    int ans = 0;

    FOR(i,1,(m-1)/2+1){
        int t = min(xm[i],xm[m-i]);
        if(xml[i]<t){
            xmp[i] -= (t-xml[i]+1)/2;
        }
        if(xml[m-i]<t){
            xmp[m-i] -= (t-xml[m-i]+1)/2;
        }
        ans += t;
    }

    ans += xmp[0] + xml[0]/2;
    if(m%2==0){
        ans += xmp[m/2] + xml[m/2]/2;
        FOR(i,1,m){
            if(i!=m/2){
                ans+=xmp[i];
            }
        }
    }else{
        FOR(i,1,m){
            ans+=xmp[i];
        }
    }





    cout << ans << endl;
    
    return 0;
}

Submission Info

Submission Time
Task D - Pair Cards
User NSTomoS
Language C++11 (GCC 4.8.1)
Score 700
Code Size 2194 Byte
Status AC
Exec Time 19 ms
Memory 4224 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 8 ms 1024 KB
01-02.txt AC 16 ms 1792 KB
01-03.txt AC 16 ms 1792 KB
01-04.txt AC 16 ms 1792 KB
01-05.txt AC 16 ms 1792 KB
01-06.txt AC 16 ms 1792 KB
01-07.txt AC 16 ms 1792 KB
01-08.txt AC 16 ms 1792 KB
01-09.txt AC 16 ms 1920 KB
01-10.txt AC 17 ms 2816 KB
01-11.txt AC 19 ms 4224 KB
01-12.txt AC 14 ms 1536 KB
01-13.txt AC 15 ms 2560 KB
01-14.txt AC 16 ms 1792 KB
01-15.txt AC 16 ms 1792 KB
01-16.txt AC 16 ms 1792 KB
01-17.txt AC 16 ms 1792 KB
01-18.txt AC 16 ms 1920 KB
01-19.txt AC 16 ms 2176 KB
01-20.txt AC 19 ms 4224 KB
01-21.txt AC 16 ms 1792 KB
01-22.txt AC 15 ms 1792 KB
01-23.txt AC 16 ms 1792 KB
01-24.txt AC 16 ms 1920 KB
01-25.txt AC 17 ms 2560 KB
01-26.txt AC 19 ms 4224 KB
01-27.txt AC 12 ms 3456 KB
01-28.txt AC 9 ms 3456 KB
01-29.txt AC 7 ms 1920 KB
01-30.txt AC 8 ms 3200 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 3 ms 256 KB