結果
問題 | No.190 Dry Wet Moist |
ユーザー |
|
提出日時 | 2016-12-12 14:06:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,757 bytes |
コンパイル時間 | 1,700 ms |
コンパイル使用メモリ | 175,172 KB |
実行使用メモリ | 22,784 KB |
最終ジャッジ日時 | 2024-11-29 15:52:55 |
合計ジャッジ時間 | 4,417 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 16 WA * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; int N; vi A; void init(){ cin >> N; A = vi( 2 * N ); for( int i = 0; i < 2 * N; ++i ) cin >> A[ i ]; } int cnt0; multiset< int > dry, wet; void preprocess(){ for( int i = 0; i < 2 * N; ++i ){ if( A[ i ] == 0 ) ++cnt0; if( A[ i ] < 0 ) dry.emplace( -A[ i ] ); if( A[ i ] > 0 ) wet.emplace( A[ i ] ); } } void solve(){ ll a = 0, b = 0, c = 0; multiset< int > d = dry, w = wet; for( auto v : dry ){ auto it = w.upper_bound( v ); if( it == w.end() ) continue; w.erase( it ); ++b; } if( cnt0 >= w.size() ) b += w.size(); else b += cnt0 + ( w.size() - cnt0 ) / 2; for( auto v : wet ){ auto it = d.upper_bound( v ); if( it == d.end() ) continue; d.erase( it ); ++a; } if( cnt0 >= d.size() ) a += w.size(); else a += cnt0 + ( d.size() - cnt0 ) / 2; d = dry, w = wet; for( auto v : dry ){ auto it = w.lower_bound( v ); if( it == w.end() ) continue; if( *it == v ) w.erase( it ), ++c; } c += cnt0 / 2; cout << a << " " << b << " " << c << endl; } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }