oj.uz

Submission #113230

# Submission time Handle Problem Language Result Execution time Memory
113230 2019-05-24T11:37:23 Z tutis Karte (COCI18_karte) C++17
120 / 120
 296 ms 8756 KB 
/*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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2040 KB Output is correct
2 Correct 33 ms 1784 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3648 KB Output is correct
2 Correct 66 ms 3072 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 8756 KB Output is correct
2 Correct 131 ms 7372 KB Output is correct