#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class DryWetMoist { public: void solve(void) { int N; cin>>N; vector A(2*N); REP(i,2*N) cin>>A[i]; // まともに計算すると O(N!) になってしまう。 // // まず Moist を最大化する組み合わせに注目する // Moist になるには (a,-a) なる組み合わせしかありえないので、 // 貪欲法で計算すればよい。ソートしておけば O(N*log(N)) で計算できる。 // // 同様に Dry なものを作るには貪欲法で a<0 のとき (a,b) (b<-a なる最大の b) // Wet なものを作るには a>0 のとき (a,b) (b>-a なる 最小の b) // なる b を選べば良い。 // これらも二分探索で O(N*log(N)) でみつかる // // multiset をつかえば配列の要素の削除・更新ができる。 // int nDry = 0; { multiset S(RANGE(A)); while (!S.empty()) { auto beg = S.begin(); int a = *beg; if (a >= 0) break; S.erase(beg); // 重複検索しないように先に削除 auto found = S.lower_bound(-a); if (found != S.begin()) { --found; assert(a+*found <0); ++nDry; S.erase(found); } } } int nWet = 0; { multiset S(RANGE(A)); while (!S.empty()) { // 大きいものから取り出す auto it = S.end(); --it; int a = *it; if (a < 0) break; S.erase(it); auto found = S.upper_bound(-a); if (found != S.end() && a + *found > 0) { ++nWet; S.erase(found); } } } int nMoist = 0; { multiset S(RANGE(A)); while (!S.empty()) { auto beg = S.begin(); int a = *beg; S.erase(beg); auto found = S.lower_bound(-a); if (found != S.end() && *found == -a) { ++nMoist; S.erase(found); } } } cout<solve(); delete obj; return 0; } #endif