Submission #1691299


Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;

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

	cin >> N >> M;
	vector<int>num(100001);
	vector<int>mod(M);
	for (int i = 0; i < N; i++) {
		cin >> K;
		num[K]++;
		mod[K%M]++;
	}
	int ans = 0;
	ans += mod[0] / 2;
	if (M % 2 == 0) {
		ans += mod[M / 2] / 2;
	}
	for (int i = 1; i < (M+1) / 2; i++) {
		K= min(mod[i], mod[M - i]);
		ans += K;
		if (!K) {
			continue;
		}
		vector<int>box;
		vector<int>bag;
		for (int j = i; j <= 100000; j += M) {
			box.push_back(num[j]);
		}
		for (int j = M - i; j <= 100000; j += M) {
			bag.push_back(num[j]);
		}
		L = 0;
		R = 0;
		for (int j = 0; j < box.size(); j++) {
			if (L == K) {
				break;
			}
			if (box[j] % 2) {
				box[j]--;
				L++;
			}
		}
		for (int j = 0; j < bag.size(); j++) {
			if (R == K) {
				break;
			}
			if (bag[j] % 2) {
				bag[j]--;
				R++;
			}
		}
		sort(box.begin(), box.end());
		reverse(box.begin(), box.end());
		sort(bag.begin(), bag.end());
		reverse(bag.begin(), bag.end());
		for (int j = 0; j < box.size(); j++) {
			if (L == K) {
				break;
			}
			int fig = min((long long int)box[j], K - L);
			L += fig;
			box[j] -= fig;
		}
		for (int j = 0; j < bag.size(); j++) {
			if (R == K) {
				break;
			}
			int fig = min((long long int)bag[j], K - R);
			R += fig;
			bag[j] -= fig;
		}
		for (int j = 0; j < box.size(); j++) {
			ans += box[j] / 2;
		}
		for (int j = 0; j < bag.size(); j++) {
			ans += bag[j] / 2;
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Pair Cards
User olphe
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1958 Byte
Status WA
Exec Time 15 ms
Memory 1148 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 26
WA × 8
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 640 KB
01-02.txt AC 10 ms 640 KB
01-03.txt AC 10 ms 640 KB
01-04.txt AC 12 ms 1148 KB
01-05.txt AC 11 ms 1024 KB
01-06.txt AC 12 ms 856 KB
01-07.txt AC 12 ms 640 KB
01-08.txt AC 12 ms 640 KB
01-09.txt AC 12 ms 640 KB
01-10.txt WA 14 ms 768 KB
01-11.txt WA 13 ms 1024 KB
01-12.txt WA 10 ms 640 KB
01-13.txt WA 10 ms 768 KB
01-14.txt AC 10 ms 640 KB
01-15.txt AC 11 ms 992 KB
01-16.txt AC 11 ms 640 KB
01-17.txt AC 11 ms 640 KB
01-18.txt AC 12 ms 640 KB
01-19.txt AC 13 ms 640 KB
01-20.txt AC 15 ms 1024 KB
01-21.txt AC 10 ms 640 KB
01-22.txt AC 11 ms 896 KB
01-23.txt AC 11 ms 640 KB
01-24.txt WA 11 ms 640 KB
01-25.txt WA 10 ms 768 KB
01-26.txt WA 10 ms 1024 KB
01-27.txt AC 6 ms 1024 KB
01-28.txt WA 2 ms 1024 KB
01-29.txt AC 1 ms 768 KB
01-30.txt AC 2 ms 1024 KB
sample-01.txt AC 3 ms 992 KB
sample-02.txt AC 2 ms 768 KB