CODE FESTIVAL 2016 Final

Submission #1732575

Source codeソースコード

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e9
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
ll n, m, x, cnt_odd[100001], cnt[100001], ans;
 
int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> x;
		cnt[x]++;
		if(cnt[x]%2){
			cnt_odd[x%m]++;
		}
		else{
			cnt_odd[x%m]--;
		}
	}
	if(m%2==0){
		x=0;
		for(int i = 0; i*m <= 100000; i++){
			x+=cnt[i*m];
		}
		ans+=x/2;
		x=0;
		for(int i = 0; i*m+m/2 <= 100000; i++){
			x+=cnt[i*m+m/2];
		}
		ans+=x/2;
		for(int i = 1; i < m/2; i++){
			x=min(cnt_odd[i],cnt_odd[m-i]);
			cnt_odd[i]-=x;
			cnt_odd[m-i]-=x;
			ans+=x;
			if(cnt_odd[i]==0 && cnt_odd[m-i]==0){
				for(int j = 0; i+j*m<=100000; j++){
					ans+=cnt[i+j*m]/2;
				}
				for(int j = 0; m-i+j*m<=100000; j++){
					ans+=cnt[m-i+j*m]/2;
				}
			}
			else if(cnt_odd[i]==0){
				for(int j = 0; i+j*m <= 100000; j++){
					if(cnt[i+j*m]%2){
						cnt[i+j*m]--;
					}
					x=min(cnt_odd[m-i],cnt[i+j*m]);
					ans+=x;
					cnt_odd[m-i]-=x;
					cnt[i+j*m]-=x;
					ans+=cnt[i+j*m]/2;
				}
				for(int j = 0; m-i+j*m <= 100000; j++){
					ans+=cnt[m-i+j*m]/2;
				}
			}
			else{
				for(int j = 0; m-i+j*m <= 100000; j++){
					if(cnt[m-i+j*m]%2){
						cnt[m-i+j*m]--;
					}
					x=min(cnt_odd[i],cnt[m-i+j*m]);
					ans+=x;
					cnt_odd[i]-=x;
					cnt[m-i+j*m]-=x;
					ans+=cnt[m-i+j*m]/2;
				}
				for(int j = 0; i+j*m <= 100000; j++){
					ans+=cnt[i+j*m]/2;
				}
			}
		}
	}
	else{
		x=0;
		for(int i = 0; i*m <= 100000; i++){
			x+=cnt[i*m];
		}
		ans+=x/2;
		for(int i = 1; i <= m/2; i++){
			x=min(cnt_odd[i],cnt_odd[m-i]);
			cnt_odd[i]-=x;
			cnt_odd[m-i]-=x;
			ans+=x;
			if(cnt_odd[i]==0 && cnt_odd[m-i]==0){
				for(int j = 0; i+j*m<=100000; j++){
					ans+=cnt[i+j*m]/2;
				}
				for(int j = 0; m-i+j*m<=100000; j++){
					ans+=cnt[m-i+j*m]/2;
				}
			}
			else if(cnt_odd[i]==0){
				for(int j = 0; i+j*m <= 100000; j++){
					if(cnt[i+j*m]%2){
						cnt[i+j*m]--;
					}
					x=min(cnt_odd[m-i],cnt[i+j*m]);
					ans+=x;
					cnt_odd[m-i]-=x;
					cnt[i+j*m]-=x;
					ans+=cnt[i+j*m]/2;
				}
				for(int j = 0; m-i+j*m <= 100000; j++){
					ans+=cnt[m-i+j*m]/2;
				}
			}
			else{
				for(int j = 0; m-i+j*m <= 100000; j++){
					if(cnt[m-i+j*m]%2){
						cnt[m-i+j*m]--;
					}
					x=min(cnt_odd[i],cnt[m-i+j*m]);
					ans+=x;
					cnt_odd[i]-=x;
					cnt[m-i+j*m]-=x;
					ans+=cnt[m-i+j*m]/2;
				}
				for(int j = 0; i+j*m <= 100000; j++){
					ans+=cnt[i+j*m]/2;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

Submission

Task問題 D - Pair Cards
User nameユーザ名 vjudge3
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 3032 Byte
File nameファイル名
Exec time実行時間 32 ms
Memory usageメモリ使用量 1792 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 32 ms 1024 KB
01-03.txt AC 31 ms 1024 KB
01-04.txt AC 31 ms 1024 KB
01-05.txt AC 31 ms 1024 KB
01-06.txt AC 31 ms 1024 KB
01-07.txt AC 31 ms 1024 KB
01-08.txt AC 31 ms 1024 KB
01-09.txt AC 31 ms 1024 KB
01-10.txt AC 32 ms 1280 KB
01-11.txt AC 32 ms 1792 KB
01-12.txt AC 31 ms 1024 KB
01-13.txt AC 31 ms 640 KB
01-14.txt AC 30 ms 1024 KB
01-15.txt AC 30 ms 1024 KB
01-16.txt AC 30 ms 1024 KB
01-17.txt AC 30 ms 1024 KB
01-18.txt AC 30 ms 1024 KB
01-19.txt AC 30 ms 1152 KB
01-20.txt AC 31 ms 1792 KB
01-21.txt AC 31 ms 1024 KB
01-22.txt AC 32 ms 1152 KB
01-23.txt AC 31 ms 1024 KB
01-24.txt AC 31 ms 1024 KB
01-25.txt AC 31 ms 1280 KB
01-26.txt AC 32 ms 1792 KB
01-27.txt AC 17 ms 1792 KB
01-28.txt AC 3 ms 1792 KB
01-29.txt AC 2 ms 1280 KB
01-30.txt AC 2 ms 1152 KB
sample-01.txt AC 2 ms 1024 KB
sample-02.txt AC 2 ms 1024 KB