Submission #113230

#	Time	Username	Problem	Language	Result	Execution time	Memory
113230		tutis	Karte (COCI18_karte)	C++17	120 / 120	296 ms	8756 KiB

karte

/*input
5 3
2
1
3
0
3
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int eval(int a[], int n)
{
	int b = 0;
	for (int i = 0; i < n; i++)
	{
		if (b < a[i])
			b++;
	}
	return b;
}
int main()
{
	clock_t pradzia = clock();
	srand(pradzia);
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	int a[n], b[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	int lo = k + 10;
	int hi = -2;
	sort(a, a + n, greater<int>());
	lo = min(lo, eval(a, n));
	sort(b, b + n, less<int>());
	hi = max(hi, eval(b, n));
	if (lo <= k && k <= hi)
	{
		while (lo < hi && lo != k && hi != k)
		{
			int c[n];
			if (rand() % 2 == 0)
				for (int i = 0; i < n; i++)
					c[i] = a[i];
			else
				for (int i = 0; i < n; i++)
					c[i] = b[i];
			for (int kiek = 0; kiek < (abs(lo - hi)) / 2; kiek++)
			{
				int i = rand() % n;
				int j = rand() % n;
				swap(c[i], c[j]);
			}
			int e = eval(c, n);
			if (lo <= e && e <= hi)
			{
				if (e >= k)
				{
					for (int i = 0; i < n; i++)
						b[i] = c[i];
					hi = e;
				}
				else
				{
					lo = e;
					for (int i = 0; i < n; i++)
						a[i] = c[i];
				}
			}
		}
		if (hi == k)
			for (int i = 0; i < n; i++)
				a[i] = b[i];
		assert(eval(a, n) == k);
		reverse(a, a + n);
		for (int i : a)
			cout << i << " ";
		cout << "\n";
		return 0;
	}
	else
		cout << "-1\n";
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12