CODE FESTIVAL 2016 Final

Submission #5538919

Source codeソースコード

// D - Pair Cards.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <numeric>


using lolo=long long;
using namespace std;
using vec=vector<lolo>;
using vvec=vector<vec>;
using vecb=vector<bool>;
#define FOR(i,n) for (lolo i=0; i<n; ++i)
#define FORN(i,a,b) for (lolo i=a; i<b; ++i)
#define REV(i,a,b) for (lolo i=a; i>b; --i)
#define ALL(x) x.begin(), x.end()

template <class T>
void chmax(T& ans, const T& b)
{
	if (ans < b) {
		ans = b;
	}
}

int main()
{
	lolo N, M;
	cin >> N >> M;
	vec X(N);
	lolo mmax = 0;
	FOR(i, N) {
		cin >> X[i];
		chmax(mmax, X[i]);
	}

	vector< map<lolo, lolo> > POOL(M, map<lolo, lolo>{});
	//vec S(mmax + 1, 0);
	vec S(M, 0);
	
	FOR(i, N) {
		S[X[i] % M ] += 1;
		//POOL[X[i] % M].push_back(X[i]);
		POOL[X[i] % M][X[i]] += 1;
	}

	//int i = 1; int j = (M - i) % M;
	int i = 0; int j = 0;
	lolo ans = 0;
	//ans += S[0] / 2;
	while (i <= j) {
		// i == j になるのは、Mが偶数の時
		if (i != j) {
			ans += min(S[i], S[j]);
			
			lolo ones = 0;
			lolo pairs = 0;
			if (S[i] > S[j]) {
				for (auto mv : POOL[ i % M]) {
					ones += (mv.second % 2 == 1) ? 1 : 0;
					pairs += mv.second / 2;
				}
			}
			else {
				for (auto mv : POOL[ j % M]) {
					ones += (mv.second % 2 == 1) ? 1 : 0;
					pairs += mv.second / 2;
				}
			}

			lolo rem = min(S[i], S[j]) - ones;
			if (rem > 0) {// ones が足りないとき
				pairs -= (rem + 1) / 2;
			}
			ans += pairs ;

			
		}
		else if ( i == j and i == 0) {
			lolo ones = 0, pairs = 0;
			for (auto mv : POOL[j  % M]) {
				ones += (mv.second % 2 == 1) ? 1 : 0;
				pairs += mv.second / 2;
			}
			//lolo rem = max(S[i], S[j]) - min(S[i], S[j]);
			//ans += pairs / 2;
			ans += S[i] / 2;
		}
		else {
			//lolo rem = max(S[i], S[j]) - min(S[i], S[j]);
			ans += S[i] / 2;

		}
		
		i += 1;
		(j = (j + M) - 1) %= M;
	}
	cout << ans << endl;

}

Submission

Task問題 D - Pair Cards
User nameユーザ名 moikilo002
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 2299 Byte
File nameファイル名
Exec time実行時間 65 ms
Memory usageメモリ使用量 12800 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
all 700 / 700 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 57 ms 4992 KB
01-03.txt AC 57 ms 4992 KB
01-04.txt AC 57 ms 4992 KB
01-05.txt AC 57 ms 4992 KB
01-06.txt AC 56 ms 4992 KB
01-07.txt AC 55 ms 4992 KB
01-08.txt AC 50 ms 4992 KB
01-09.txt AC 50 ms 5120 KB
01-10.txt AC 42 ms 7168 KB
01-11.txt AC 42 ms 10496 KB
01-12.txt AC 31 ms 1024 KB
01-13.txt AC 32 ms 3456 KB
01-14.txt AC 65 ms 7296 KB
01-15.txt AC 62 ms 7296 KB
01-16.txt AC 60 ms 7296 KB
01-17.txt AC 57 ms 7296 KB
01-18.txt AC 55 ms 7424 KB
01-19.txt AC 50 ms 7936 KB
01-20.txt AC 45 ms 12800 KB
01-21.txt AC 38 ms 1280 KB
01-22.txt AC 37 ms 1280 KB
01-23.txt AC 36 ms 1280 KB
01-24.txt AC 33 ms 1280 KB
01-25.txt AC 32 ms 2944 KB
01-26.txt AC 35 ms 6784 KB
01-27.txt AC 24 ms 9216 KB
01-28.txt AC 6 ms 5888 KB
01-29.txt AC 3 ms 2432 KB
01-30.txt AC 5 ms 5760 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB