Submission #11212345
Source Code Expand
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <string> #include <math.h> #include <iomanip> #include <limits> #include <list> #include <queue> #include <tuple> #include <map> #include <stack> #include <set> #include <bitset> #include <functional> using namespace std; #define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ; #define ll long long int #define rep(i,n) for(int i=0; i<(int)(n); i++) #define reps(i,n) for(int i=1; i<=(int)(n); i++) #define REP(i,n) for(int i=n-1; i>=0; i--) #define REPS(i,n) for(int i=n; i>0; i--) #define MOD (long long int)(1e9+7) #define INF (int)(1123456789) #define LINF (long long int)(112345678901234567) #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) #define all(v) v.begin(), v.end() typedef pair<int, int> Pii; typedef pair<ll, ll> Pll; ll mpow(ll a, ll b){ if(b==0) return 1; else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;} else return mpow(a,b-1) * a % MOD; } ll lpow(ll a, ll b){ if(b==0) return 1; else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;} else return lpow(a,b-1) * a; } ll gcd(ll a, ll b){ if(b==0) return a; else return gcd(b, a%b); } vector<ll> kaijo_memo; ll kaijo(ll n){ if(kaijo_memo.size() > n) return kaijo_memo[n]; if(kaijo_memo.size() == 0) kaijo_memo.push_back(1); while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD); return kaijo_memo[n]; } vector<ll> gyaku_kaijo_memo; ll gyaku_kaijo(ll n){ if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n]; if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1); while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD); return gyaku_kaijo_memo[n]; } ll nCr(ll n, ll r){ if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く?不安. if(n < r || r < 0) return 0; ll ret = 1; if(n <= 1e7){ ret *= kaijo(n); ret %= MOD; ret *= gyaku_kaijo(r); ret %= MOD; ret *= gyaku_kaijo(n-r); ret %= MOD; }else{ rep(i,r){ ret *= n-i; ret %= MOD; ret *= mpow(r-i, MOD-2); ret %= MOD; } } return ret; } int main(void){ fast_io cout<<fixed<<setprecision(15); ll n,m;cin>>n>>m; map<ll,map<ll,ll>> mp; rep(i,n){ ll x;cin>>x; mp[x%m]; mp[x%m][x]++; mp[x%m][-1]++; } ll ans = 0; rep(x, m){ if(x*2 > m){ break; } if(x == 0 || x*2 == m){ ans += mp[x][-1]/2; continue; } ll l = x; ll r = m - x; if(mp[l][-1] < mp[r][-1]){ swap(l,r); } //l >= r for(auto itr2 = mp[l].begin(); itr2 != mp[l].end(); itr2++){ if(itr2->first == -1) continue; if(mp[l][-1] <= mp[r][-1]){ break; } while(mp[l][-1] > mp[r][-1] && itr2->second >= 2){ itr2->second -= 2; mp[l][-1] -= 2; ans++; } } ans += min(mp[l][-1], mp[r][-1]); } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Pair Cards |
User | Jirotech |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 3208 Byte |
Status | AC |
Exec Time | 152 ms |
Memory | 22144 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, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 41 ms | 4224 KB |
01-03.txt | AC | 41 ms | 4224 KB |
01-04.txt | AC | 43 ms | 4224 KB |
01-05.txt | AC | 43 ms | 4224 KB |
01-06.txt | AC | 46 ms | 4224 KB |
01-07.txt | AC | 46 ms | 4224 KB |
01-08.txt | AC | 55 ms | 4352 KB |
01-09.txt | AC | 57 ms | 4480 KB |
01-10.txt | AC | 91 ms | 10496 KB |
01-11.txt | AC | 130 ms | 19840 KB |
01-12.txt | AC | 13 ms | 256 KB |
01-13.txt | AC | 50 ms | 7168 KB |
01-14.txt | AC | 47 ms | 6528 KB |
01-15.txt | AC | 51 ms | 6528 KB |
01-16.txt | AC | 57 ms | 6528 KB |
01-17.txt | AC | 65 ms | 6528 KB |
01-18.txt | AC | 68 ms | 6912 KB |
01-19.txt | AC | 70 ms | 8448 KB |
01-20.txt | AC | 152 ms | 22144 KB |
01-21.txt | AC | 23 ms | 512 KB |
01-22.txt | AC | 24 ms | 512 KB |
01-23.txt | AC | 26 ms | 512 KB |
01-24.txt | AC | 35 ms | 640 KB |
01-25.txt | AC | 55 ms | 5248 KB |
01-26.txt | AC | 90 ms | 16128 KB |
01-27.txt | AC | 112 ms | 19072 KB |
01-28.txt | AC | 53 ms | 16128 KB |
01-29.txt | AC | 17 ms | 6528 KB |
01-30.txt | AC | 60 ms | 15872 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |