Submission #994845

---

Source Code Expand

#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;
const int M = 1e9 + 7;
#pragma unused(M)

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> vec;
    map<int, map<int, int>> nums;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        vec.emplace_back(x % m, x);
        nums[x % m][x]++;
    }
    // sort(vec.begin(), vec.end());

    // int num = vec[1].second;
    // int num2 = lower_bound(vec.begin(), vec.end(), pair<int, int>{m - num, -1}) -> second;
    // cout<<num<<' '<<num2<<endl;
    // println(nums);
    int ans = 0;

    for(int i=0;i<m;i++){
        if(i == (m - i) % m){
            ans += nums[i].size() / 2;
        }else{
            if(i > (m - i) % m){ break; }
            if(!nums.count(i) || !nums.count((m - i) % m)){ continue; }
            auto& m1 = nums[i];
            auto& m2 = nums[(m - i) % m];
            int s1 = 0, s2 = 0;
            for(auto& p : m1){ s1 += p.second; }
            for(auto& p : m2){ s2 += p.second; }
            ans += min(s1, s2);
            if(s1 == s2){ continue; }
            if(s1 < s2){
                swap(s1, s2);
                swap(m1, m2);
            }
            if(s1 > s2){
                vector<int> v;
                for(auto& p : m1){ v.push_back(p.second); }
                sort(v.begin(), v.end());
                for(int& i : v){
                    int d = min(i, s2);
                    s2 -= d;
                    i -= d;
                }
                for(int& i : v){
                    ans += i / 2;
                }
            // }else{
            }
        }
    }
    cout << ans << endl;
    return 0;

    bool changed = true;
    while(changed){
        changed = false;
        for(int i=0;i<m;i++){
            if(!nums.count(i) || !nums.count((m - i) % m)){ continue; }

            auto p1 = nums[i].begin(), p2 = nums[(m - i) % m].begin();
            while(p1 != nums[i].end() && p1 -> second != 1){ p1++; }
            if(p1 == nums[i].end()){ continue; }
            int n1 = p1 -> first;
            while(p2 != nums[(m - i) % m].end() && (p2 -> second == 0 || n1 == p2 -> first)){ p2++; }
            if(p2 == nums[(m - i) % m].end()){ continue; }
            int n2 = p2 -> first;

            // cout<<n1<<' '<<n2<<endl;
            if(n1 != n2){
                nums[i][n1]--;
                nums[(m - i) % m][n2]--;
                // cout<<' '<<n1<<' '<<n2<<endl;
                ans++;
                changed = true;
                i--;
            }
        }
    }

    for(int i=0;i<m;i++){
        if(!nums.count(i) || !nums.count((m - i) % m)){ continue; }

        auto p1 = nums[i].begin(), p2 = nums[(m - i) % m].begin();
        while(p1 != nums[i].end() && p1 -> second == 0){ p1++; }
        if(p1 == nums[i].end()){ continue; }
        int n1 = p1 -> first;
        while(p2 != nums[(m - i) % m].end() && (p2 -> second == 0 || n1 == p2 -> first)){ p2++; }
        if(p2 == nums[(m - i) % m].end()){ continue; }
        int n2 = p2 -> first;

        // cout<<n1<<' '<<n2<<endl;
        if(n1 != n2){
            nums[i][n1]--;
            nums[(m - i) % m][n2]--;
            // cout<<' '<<n1<<' '<<n2<<endl;
            ans++;
            i--;
        }
    }

    for(int i=0;i<m;i++){
        if(!nums.count(i)){ continue; }
        for(auto& p : nums[i]){
            if(p.second >= 2){
                ans += p.second / 2;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result