|
|
back to boardO(NlogN) C++ soluton Posted by Maxim 13 Feb 2014 03:02 /* * File: main.cpp * Author: Maxim Cherchuk <maxim.cherchuk@gmail.com> * * Created on 12 Февраль 2014 г., 23:36 */ #include <iostream> #include <algorithm> using namespace std; /* * */ const int MAXN = 50000, MAX = 10000; int a[MAXN], b[MAXN]; int n, k, m; int main(int argc, char** argv) { ios_base::sync_with_stdio(0); cin >> n; for(int i = 0; i < n; ++i) { cin >> a[i]; } cin >> k; for(int i = 0; i < k; ++i) { cin >> b[i]; } sort(a, a+n); sort(b, b+k); for(int i = 0; i < n; ++i) { const int cur = a[i]; int l = 0; int r = k; while(r-l > 1) { // binary search m = (l+r)>>1; if(cur+b[m] > MAX) r = m; else l = m; } if(cur + b[l] == MAX) { cout << "YES"; return 0; } } cout << "NO"; } |
|
|