sqrt_knapsack.cpp

#include <iostream>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = (1e5) + 1;
int dp[maxn];
int pr[maxn];
int a[maxn];
map <int, int> mp;
vector <pair <int, int> > v;

int main()
{
	freopen("parties.in", "r", stdin);
	freopen("parties.out", "w", stdout);
	int n;
	
	scanf("%d", &n);
	clock_t t = clock();
	for (int i = 0; i < n; i++)
	{
		int k;
		scanf("%d", &k);
		a[i] = k;
		mp[k + 1]++;
	}
	
	//O(sqrt(n))
	for (auto it = mp.begin(); it != mp.end(); it++) //mp size can not be more than sqrt(n)
		v.push_back(*it);

	for (int i = 1; i <= n; i++)
		dp[i] = -1;

	for (int z = 0; z < v.size(); z++)
	{
		int len = v[z].first;
		int cnt = v[z].second;
		for (int x = 0; x + v[z].first <= n; x++)
		{
			int y = x + len;
			if (dp[x] != -1 && dp[y] == -1)
			{
				if (pr[x] != len)
					dp[y] = 1, pr[y] = len;
				else
					if (dp[x] < cnt)
						dp[y] = dp[x] + 1, pr[y] = len;
			}
		}
	}
	
	if (dp[n] == -1)
		puts("NO");
	else
	{
		multiset <int> ans;
		puts("YES");
		int cur = n;
		while (cur > 0)
		{
			ans.insert(pr[cur]);
			cur = cur - pr[cur];
		}
		for (int i = 0; i < n; i++)
		{
			auto it = ans.lower_bound(a[i] + 1);
			if (it == ans.end() || *it != (a[i] + 1))
				printf("2 ");
			else
				printf("1 "), ans.erase(it);
		}
	}

	cerr << float(clock() - t) / CLOCKS_PER_SEC;
	return 0;
}