oj.uz

Submission #113229

# Submission time Handle Problem Language Result Execution time Memory
113229 2019-05-24T11:36:08 Z tutis Karte (COCI18_karte) C++17
84 / 120
 1000 ms 6140 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];
			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 3 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 2 ms 384 KB Output is correct

Subtask #4
12.0 / 12.0

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

Subtask #5
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 #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 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 3 ms 356 KB Output is correct

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 1540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 2680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 6140 KB Time limit exceeded
2 Halted 0 ms 0 KB -