Submission #993921
Source Code Expand
#include <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
// #define DEBUG
#ifdef DEBUG
#define dump(...) fprintf(stderr, __VA_ARGS__)
#else
#define dump(...)
#endif
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);
const int N = 1e5 + 1;
int cnt_num[N];
int main(void){
cin.tie(0);
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
vi x(n); for(auto& e : x) cin >> e, cnt_num[e]++;
uniq(x);
for(auto & e : x) cerr << e << " ";
cerr << endl;
vector<vi> tbl(m);
rep(i, x.size()){
int e = x[i];
tbl[e % m].push_back(cnt_num[e]);
}
rep(i, m){
sort(_all(tbl[i]));
}
int res = 0;
rep(i, m){
cerr << i << ": " << endl;
cerr << "res = " << res << endl;
int j = (m - i + m) % m;
if(j == i){
cerr << "hoge" << endl;
int sum = 0;
for(auto e : tbl[i]) sum += e;
res += sum / 2;
continue;
}
if(j < i) break;
vi& a = tbl[i];
vi& b = tbl[j];
for(auto e : a) {
cerr << e << " ";
}
cerr << endl;
for(auto e : b) {
cerr << e << " ";
}
cerr << endl;
int suma = 0, sumb = 0;
for(auto& e : a) suma += e;
for(auto& e : b) sumb += e;
if(suma < sumb){
swap(a, b);
swap(suma, sumb);
}
res += sumb;
int rest = sumb;
{
int ai = 0;
while(rest >= 1){
while(ai < a.size() and a[ai] % 2 == 0){
ai++;
}
if(ai >= a.size()) break;
a[ai]--;
rest--;
}
}
rep(ai, a.size()){
int diff = min(rest, a[ai]);
a[ai] -= diff;
rest -= diff;
}
assert(rest == 0);
rep(ai, a.size()){
cerr << "a[ai] = " << a[ai] << endl;
res += a[ai] / 2;
cerr << "! " << res << endl;
}
}
cout << res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Pair Cards |
User |
nokoTaro |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3743 Byte |
Status |
AC |
Exec Time |
1233 ms |
Memory |
6528 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 |
159 ms |
1408 KB |
01-03.txt |
AC |
157 ms |
1408 KB |
01-04.txt |
AC |
388 ms |
1536 KB |
01-05.txt |
AC |
327 ms |
1408 KB |
01-06.txt |
AC |
475 ms |
1408 KB |
01-07.txt |
AC |
479 ms |
1536 KB |
01-08.txt |
AC |
512 ms |
1408 KB |
01-09.txt |
AC |
521 ms |
1536 KB |
01-10.txt |
AC |
761 ms |
3072 KB |
01-11.txt |
AC |
1016 ms |
5376 KB |
01-12.txt |
AC |
12 ms |
640 KB |
01-13.txt |
AC |
203 ms |
1664 KB |
01-14.txt |
AC |
240 ms |
1660 KB |
01-15.txt |
AC |
677 ms |
1736 KB |
01-16.txt |
AC |
753 ms |
1792 KB |
01-17.txt |
AC |
785 ms |
1536 KB |
01-18.txt |
AC |
811 ms |
1920 KB |
01-19.txt |
AC |
840 ms |
2048 KB |
01-20.txt |
AC |
1233 ms |
6528 KB |
01-21.txt |
AC |
25 ms |
1024 KB |
01-22.txt |
AC |
43 ms |
1024 KB |
01-23.txt |
AC |
46 ms |
1024 KB |
01-24.txt |
AC |
54 ms |
1152 KB |
01-25.txt |
AC |
190 ms |
1920 KB |
01-26.txt |
AC |
497 ms |
3456 KB |
01-27.txt |
AC |
993 ms |
4608 KB |
01-28.txt |
AC |
477 ms |
3072 KB |
01-29.txt |
AC |
183 ms |
1664 KB |
01-30.txt |
AC |
436 ms |
2688 KB |
sample-01.txt |
AC |
2 ms |
256 KB |
sample-02.txt |
AC |
2 ms |
256 KB |