Submission #64136089

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int mod = 998244353;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}

int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}

int mult(int a, int b)
{
	return (LL)a * b % mod;
}

int binpow(int a, LL n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

template<typename T>
void updMin(T& a, T b)
{
	a = min(a, b);
}

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	int n;
	cin >> n;
	VI a(n), b(n);
	VI va, vb;
	int c = 0;
	unordered_map<int, int> ca, cb, cs;
	for (int& ai : a)
	{
		cin >> ai;
		if (ai == -1)
			c++;
		else
		{
			va.PB(ai);
			ca[ai]++;
		}
	}
	for (int& bi : b)
	{
		cin >> bi;
		if (bi == -1)
			c++;
		else
		{
			vb.PB(bi);
			cb[bi]++;
		}
	}
	if (c >= n)
	{
		cout << "Yes\n";
		return 0;
	}
	sort(ALL(va));
	sort(ALL(vb));
	for (auto [x, cx] : ca)
	{
		for (auto [y, cy] : cb)
		{
			cs[x + y] += min(cx, cy);
		}
	}
	vector<PII> cands;
	for (auto [z, cz] : cs)
	{
		cands.PB({cz, z});
	}
	sort(ALL(cands), greater());
	auto check = [&](int s)
	{
		int ptr = SZ(vb) - 1;
		int matched = 0;
		for (int x : va)
		{
			while (ptr >= 0 && x + vb[ptr] > s)
				ptr--;
			if (ptr >= 0 && x + vb[ptr] == s)
			{
				matched++;
				ptr--;
			}
		}
		return matched + c >= n;
	};
	FOR(i, 0, SZ(cands))
	{
		if (i % 1000 == 0 && (db)clock() / CLOCKS_PER_SEC > 4)
			break;
		int s = cands[i].S;
		if (va.back() <= s && vb.back() <= s && check(s))
		{
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
	return 0;
}

Submission Info

Judge Result