Submission #994109
Source Code Expand
#include <bits/stdc++.h>
#define int long long
#define range(i,x,y) i=(x);i<(y);i++
#define rep(i,n) for(int i=0,i##_len=n;i<i##_len;i++)
#define all(x) begin(x),end(x)
#define lim(x,r,l) (r<=x&&x<l)
typedef long long ll;
typedef long double ld;
using namespace std;
int solve(multiset<int> a, multiset<int> b){
int aod = 0, bod = 0;
for(auto aa: a) {
//cout <<"a" << aa ;
if(aa % 2 == 1) aod++;
}
for(auto bb: b){
//cout <<"b" << bb;
if(bb % 2 == 1) bod++;
}
// cout <<endl;
if(aod > bod){
swap(aod, bod); swap(a, b);
}
//aod <= bod
int bipaired = aod;
multiset<int> ca, cb, ccb;
for(auto aa : a){
ca.insert(aa/2*2);
}
int suma = 0;
for(auto aa: ca){
suma += aa;
}//cout << endl;
int tmpb = bipaired;
//cout <<"B"; for(auto bb:b)cout <<bb <<","; cout << endl;
for(auto& bb : b){
if(tmpb > 0 && bb%2==1) {
cb.insert(bb-1);
tmpb--;
}else{
cb.insert(bb);
}
}
//cout <<"CB"; for(auto bb:cb)cout <<bb <<","; cout << endl;
int bpar = 0;
//cout << suma << endl;
for(auto& bb : cb){
if(suma > 0 && bb%2==1) {
ccb.insert(bb-1);
suma--;
bpar ++;
}else{
ccb.insert(bb);
}
}
//cout <<"CCB"; for(auto bb:ccb)cout <<bb <<","; cout << endl;
int res = 0;
for(auto bb: ccb){
res += bb / 2;
}
//cout << bipaired << "," << suma << "B" << bpar << endl;
//cout << "R" << res << endl;
return bipaired + (suma / 2) + res + bpar;
}
/*
signed main(){
int n, m; cin >> n >> m;
multiset<int> a, b;
rep(i,n) {int aa; cin >> aa; a.insert(aa);}
rep(i,m) {int bb; cin >> bb; b.insert(bb);}
cout << "RES" << solve(a, b) << endl;
return 0;
}
*/
signed main(){
int n, m; cin >> n >> m;
vector<int> x(n);
vector<map<int,int>> mods(m, map<int,int>());
rep(i, n){
int xx; cin >> xx;
x[i] = xx;
auto& mm = mods[xx%m];
if(mm.count(xx) == 0){
mm[xx] = 1;
}else{
mm[xx]++;
}
}
vector<multiset<int>> modn(m, multiset<int>());
rep(i, m){
for(auto kv : mods[i]){
int num, cnt; tie(num, cnt) = kv;
modn[i].insert(cnt);
}
}
int res = 0;
{
int ss = 0;
for(auto aa: modn[0]) ss += aa;
res += ss/2;
}
if(m % 2 == 0){
int ss = 0;
for(auto aa: modn[m/2]) ss += aa;
res += ss/2;
}
//cout << "PRE" << res << endl;
rep(i, (m - 1) / 2){
res += solve(modn[i + 1], modn[m - i - 1]);
}
cout << res << endl;
}
Submission Info
Submission Time |
|
Task |
D - Pair Cards |
User |
wass80 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2587 Byte |
Status |
AC |
Exec Time |
119 ms |
Memory |
21376 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
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 |
2 ms |
256 KB |
01-02.txt |
AC |
84 ms |
7936 KB |
01-03.txt |
AC |
82 ms |
7936 KB |
01-04.txt |
AC |
96 ms |
12928 KB |
01-05.txt |
AC |
93 ms |
11648 KB |
01-06.txt |
AC |
90 ms |
9344 KB |
01-07.txt |
AC |
87 ms |
8448 KB |
01-08.txt |
AC |
77 ms |
8064 KB |
01-09.txt |
AC |
78 ms |
8064 KB |
01-10.txt |
AC |
66 ms |
11648 KB |
01-11.txt |
AC |
71 ms |
17280 KB |
01-12.txt |
AC |
32 ms |
1024 KB |
01-13.txt |
AC |
39 ms |
5120 KB |
01-14.txt |
AC |
99 ms |
11904 KB |
01-15.txt |
AC |
119 ms |
16640 KB |
01-16.txt |
AC |
107 ms |
12416 KB |
01-17.txt |
AC |
95 ms |
12032 KB |
01-18.txt |
AC |
86 ms |
12288 KB |
01-19.txt |
AC |
79 ms |
13184 KB |
01-20.txt |
AC |
83 ms |
21376 KB |
01-21.txt |
AC |
49 ms |
1408 KB |
01-22.txt |
AC |
48 ms |
1536 KB |
01-23.txt |
AC |
42 ms |
1536 KB |
01-24.txt |
AC |
38 ms |
1536 KB |
01-25.txt |
AC |
39 ms |
4352 KB |
01-26.txt |
AC |
47 ms |
10752 KB |
01-27.txt |
AC |
48 ms |
15488 KB |
01-28.txt |
AC |
17 ms |
9984 KB |
01-29.txt |
AC |
8 ms |
3968 KB |
01-30.txt |
AC |
15 ms |
9600 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |