Submission #993633
Source Code Expand
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; #define MAX 100010 int N,M,X[MAX],used_counter[MAX], mod_counter[MAX]; set<int> freq_set[MAX]; // TODO :: 1 のときバグらないかチェック void compute() { map<int,int> freq; rep(i,N) { ++mod_counter[X[i]%M]; freq_set[X[i]%M].insert(X[i]); ++freq[X[i]]; } map<int,bool> is_odd; rep(i,N) { if( freq[X[i]] % 2 == 1 ) is_odd[X[i]] = true; else is_odd[X[i]] = false; } int answer = 0; rep(i,(int)(M/2)+1) { if( i == 0 ) { int use = (int)(mod_counter[i]/2); answer += use; used_counter[i] += use; continue; } int half = M - i; if( half == i ) { int use = (int)(mod_counter[i]/2); used_counter[half] += ( use * 2 ); answer += use; // cout << half << " :MID: use = " << use << "| answer = " << answer<< endl; } else { int use = min(mod_counter[half],mod_counter[i]); used_counter[half] += use; used_counter[i] += use; answer += use; /* cout << "mod_counter[" << half << "] = " << mod_counter[half] << endl; cout << "mod_counter[" << i << "] = " << mod_counter[i] << endl; cout << half << " :half: use = " << use << endl; cout << i << " :i : use = " << use << " | answer = " << answer<< endl; */ } //puts(""); } //cout << "中間発表 :: " << answer << endl; REP(i,1,M) { int remain = used_counter[i]; for(set<int>::iterator it=freq_set[i].begin();it!=freq_set[i].end();++it) { if( remain <= 0 ) break; int v = *it; if( is_odd[v] ) { --remain; --freq[v]; assert( freq[v] >= 0 ); } } for(set<int>::iterator it=freq_set[i].begin();it!=freq_set[i].end();++it) { int v = *it; int cnt = freq[v]; if( remain ) { assert( cnt % 2 == 0 ); int sub = min(remain,cnt); cnt -= sub; remain -= sub; } assert( cnt >= 0 ); answer += (int)(cnt/2); } assert(remain == 0); } cout << answer << endl; } int bf() { vector<int> vec; rep(i,N) vec.push_back(X[i]); sort(vec.begin(),vec.end()); int maxi = 0; do { int cnt = 0; for(int i=0;i<N;i+=2) { if( i+1 <(int)N && ( (vec[i]+vec[i+1]) % M == 0 || vec[i] == vec[i+1] ) ) { ++cnt; } } /* rep(i,N) { cout << vec[i] << ","; } puts(""); */ maxi = max(maxi,cnt); } while( next_permutation(vec.begin(),vec.end()) ); return maxi; } int main(){ srand((unsigned int)time(NULL)); /* N = 8; cout << N << " " << ( M = 4 ) << endl; rep(i,N) { if( i ) cout << " "; cout << rand() % 10 +1; } puts(""); return 0; */ cin >> N >> M; rep(i,N) cin >> X[i]; //cout << "Answer = " << bf() << endl; compute(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Pair Cards |
User | ChiyomiAnzai |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 3005 Byte |
Status | AC |
Exec Time | 249 ms |
Memory | 20224 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 | 7 ms | 4992 KB |
01-02.txt | AC | 141 ms | 14208 KB |
01-03.txt | AC | 155 ms | 14208 KB |
01-04.txt | AC | 163 ms | 14208 KB |
01-05.txt | AC | 165 ms | 14208 KB |
01-06.txt | AC | 181 ms | 14208 KB |
01-07.txt | AC | 182 ms | 14208 KB |
01-08.txt | AC | 177 ms | 14208 KB |
01-09.txt | AC | 173 ms | 14208 KB |
01-10.txt | AC | 144 ms | 14592 KB |
01-11.txt | AC | 154 ms | 14976 KB |
01-12.txt | AC | 37 ms | 5504 KB |
01-13.txt | AC | 37 ms | 5504 KB |
01-14.txt | AC | 198 ms | 19456 KB |
01-15.txt | AC | 205 ms | 19328 KB |
01-16.txt | AC | 238 ms | 19328 KB |
01-17.txt | AC | 243 ms | 19456 KB |
01-18.txt | AC | 249 ms | 19456 KB |
01-19.txt | AC | 207 ms | 19456 KB |
01-20.txt | AC | 183 ms | 20224 KB |
01-21.txt | AC | 76 ms | 5888 KB |
01-22.txt | AC | 77 ms | 5888 KB |
01-23.txt | AC | 75 ms | 5888 KB |
01-24.txt | AC | 71 ms | 5888 KB |
01-25.txt | AC | 67 ms | 6144 KB |
01-26.txt | AC | 69 ms | 6656 KB |
01-27.txt | AC | 81 ms | 12800 KB |
01-28.txt | AC | 12 ms | 6144 KB |
01-29.txt | AC | 8 ms | 5376 KB |
01-30.txt | AC | 8 ms | 5376 KB |
sample-01.txt | AC | 7 ms | 4992 KB |
sample-02.txt | AC | 7 ms | 4992 KB |