QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#867815#6116. Changing the Sequencesasdfsdf#AC ✓50ms6384kbC++202.7kb2025-01-24 01:36:232025-01-24 01:36:23

Judging History

This is the latest submission verdict.

  • [2025-01-24 01:36:23]
  • Judged
  • Verdict: AC
  • Time: 50ms
  • Memory: 6384kb
  • [2025-01-24 01:36:23]
  • Submitted

answer

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

#define MAX 101010
typedef pair<int, int> pii;
typedef long long ll;

template<class T>
tuple<T, vector<int>, vector<int>> hungarian_weighted_bipartite_matching(vector<vector<T>> a) {
	if (a.empty()) return { 0, {}, {} };
	bool swapped = false;
	int n = (int)a.size() + 1, m = (int)a[0].size() + 1;
	for (auto i = 0; i < n - 1; ++i) for (auto j = 0; j < m - 1; ++j) a[i][j] = -a[i][j];
	if (n > m) {
		swap(n, m);
		swapped = true;
		vector b(n - 1, vector<T>(m - 1));
		for (auto i = 0; i < n - 1; ++i) for (auto j = 0; j < m - 1; ++j) b[i][j] = a[j][i];
		swap(a, b);
	}
	vector<T> u(n), v(m);
	vector<int> p(m), mu(n - 1);
	for (auto i = 1; i < n; ++i) {
		p[0] = i;
		int j0 = 0; // add "dummy" worker 0
		vector<T> dist(m, numeric_limits<T>::max());
		vector<int> pv(m, -1), done(m + 1);
		do { // dijkstra
			done[j0] = true;
			int i0 = p[j0], j1;
			T delta = numeric_limits<T>::max();
			for (auto j = 1; j < m; ++j) if (!done[j]) {
				T cur = a[i0 - 1][j - 1] - u[i0] - v[j];
				if (cur < dist[j]) dist[j] = cur, pv[j] = j0;
				if (dist[j] < delta) delta = dist[j], j1 = j;
			}
			for (auto j = 0; j < m; ++j) {
				if (done[j]) u[p[j]] += delta, v[j] -= delta;
				else dist[j] -= delta;
			}
			j0 = j1;
		} while (p[j0]);
		while (j0) { // update alternating path
			int j1 = pv[j0];
			p[j0] = p[j1], j0 = j1;
		}
	}
	vector<int> mv(m - 1, -1);
	for (auto j = 1; j < m; ++j) if (p[j]) mu[p[j] - 1] = j - 1, mv[j - 1] = p[j] - 1;
	if (swapped) swap(mu, mv);
	return { v[0], mu, mv };
}

int A[MAX], B[MAX];

int C[70][70];
int bana[MAX];
int banb[MAX];

int pa[MAX], pb[MAX];

int P[MAX];

signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M;
	cin >> N >> M;
	int i, j;
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) cin >> B[i], C[A[i]][B[i]]++;
	auto f = [&]() {
		int i, j;
		int cnt = 0;
		for (i = 1; i <= M; i++) {
			if (!bana[i]) pa[i] = cnt++;
		}
		cnt = 0;
		for (i = 1; i <= M; i++) {
			if (!banb[i]) pb[i] = cnt++;
		}
		vector<vector<int>> mp(cnt, vector<int>(cnt));
		for (i = 1; i <= M; i++) {
			if (bana[i]) continue;
			for (j = 1; j <= M; j++) {
				if (banb[j]) continue;
				mp[pa[i]][pb[j]] = C[i][j];
			}
		}
		return get<0>(hungarian_weighted_bipartite_matching(mp));
		};
	int mn = f();
	int csum = 0;
	for (i = 1; i <= N; i++) {
		int a = A[i];
		if (bana[a]) continue;
		for (j = 1; j <= M; j++) {
			if (banb[j]) continue;
			bana[a] = 1;
			banb[j] = 1;
			if (f() + csum + C[a][j] < mn) {
				bana[a] = 0;
				banb[j] = 0;
			}
			else {
				csum += C[a][j];
				P[a] = j;
				break;
			}
		}
	}
	for (i = 1; i <= N; i++) cout << P[A[i]] << ' ';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

input:

4 3
2 2 3 3
2 2 2 2

output:

1 1 2 2 

result:

ok 4 number(s): "1 1 2 2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

5 3
2 2 3 3 2
2 2 2 2 3

output:

3 3 2 2 3 

result:

ok 5 number(s): "3 3 2 2 3"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

1 1
1
1

output:

1 

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 11ms
memory: 3840kb

input:

1 60
60
60

output:

60 

result:

ok 1 number(s): "60"

Test #5:

score: 0
Accepted
time: 11ms
memory: 5760kb

input:

1 60
1
60

output:

60 

result:

ok 1 number(s): "60"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

1 60
60
1

output:

1 

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 5860kb

input:

1 60
1
1

output:

1 

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 50ms
memory: 6256kb

input:

100000 60
18 36 47 52 31 3 43 49 2 4 60 23 22 3 4 25 11 50 25 40 51 51 59 5 11 50 47 28 29 21 46 39 46 49 23 50 1 24 15 30 45 12 5 2 4 33 23 29 35 35 47 13 10 24 20 44 23 16 27 4 25 27 47 27 57 47 35 31 24 47 27 17 45 44 29 44 43 4 23 20 22 43 2 53 41 32 56 21 28 56 21 15 44 60 11 52 36 26 33 26 4 5...

output:

41 3 18 55 15 53 21 43 48 35 24 38 12 53 35 1 39 14 1 58 10 10 2 46 39 14 18 45 50 22 27 25 27 43 38 14 20 47 42 32 40 16 46 48 35 57 38 50 44 44 18 56 7 47 23 59 38 8 33 35 1 33 18 33 30 18 44 15 47 18 33 51 40 59 50 59 21 35 38 23 12 21 48 52 28 34 9 22 45 9 22 42 59 24 39 55 3 49 57 49 35 2 36 58...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 40ms
memory: 6244kb

input:

100000 60
37 27 39 34 37 30 10 48 18 9 53 12 43 12 34 32 49 51 39 47 58 52 20 47 35 37 19 31 23 57 32 28 7 52 41 1 15 22 26 53 55 52 23 46 15 49 5 14 49 2 59 36 45 8 29 20 17 47 32 14 22 34 50 13 11 58 19 38 54 22 22 54 36 12 43 57 2 24 2 9 39 41 55 54 21 26 47 40 32 40 36 19 10 20 50 46 25 23 27 16...

output:

24 48 52 8 24 41 10 53 13 31 7 58 45 58 8 32 38 39 52 54 3 56 37 54 23 24 26 15 20 14 32 21 43 56 29 17 1 35 30 7 57 56 20 16 1 38 25 5 38 49 2 34 6 51 11 37 60 54 32 5 35 8 59 46 9 3 26 55 27 35 35 27 34 58 45 14 49 33 49 31 52 29 57 27 50 30 54 36 32 36 34 26 10 37 59 16 40 20 48 47 43 6 47 37 5 5...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 43ms
memory: 4480kb

input:

100000 60
44 14 37 1 28 26 42 20 12 32 6 52 36 2 26 57 31 24 52 45 31 20 6 31 23 28 21 47 59 14 9 41 21 22 13 21 55 47 53 23 40 34 36 52 11 56 58 57 51 48 10 37 22 58 58 41 46 17 55 4 49 18 15 23 15 39 28 29 15 12 26 21 27 60 27 58 45 21 21 41 4 55 36 39 44 26 30 23 49 21 59 58 24 19 52 47 44 19 5 4...

output:

46 11 40 3 21 53 38 37 35 50 39 15 51 6 53 56 17 8 15 9 17 37 39 17 5 21 45 60 1 11 4 57 45 41 34 45 13 60 10 5 20 19 51 15 27 44 28 56 16 14 18 40 41 28 28 57 32 7 13 12 59 24 54 5 54 25 21 31 54 35 53 45 52 22 52 28 9 45 45 57 12 13 51 25 46 53 36 5 59 45 1 28 8 26 15 60 46 26 58 59 30 34 1 24 58 ...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 38ms
memory: 4480kb

input:

90568 60
17 21 2 31 6 32 43 4 58 16 16 52 21 60 45 25 16 28 12 32 2 44 45 9 5 14 40 40 37 51 54 5 41 6 9 16 9 19 46 32 3 16 20 27 17 39 51 1 49 24 28 34 50 45 34 60 52 31 1 49 16 24 51 19 7 8 41 10 47 17 9 33 32 5 40 40 55 21 6 47 45 55 16 50 57 15 59 51 29 4 18 44 28 47 48 19 50 15 12 37 25 3 33 8 ...

output:

14 12 41 8 34 3 49 2 30 40 40 27 12 10 56 47 40 50 58 3 41 54 56 53 39 42 28 28 36 26 45 39 55 34 53 40 53 1 57 3 5 40 44 15 14 25 26 11 48 38 50 59 29 56 59 10 27 8 11 48 40 38 26 1 20 24 55 16 51 14 53 23 3 39 28 28 35 12 34 51 56 35 40 29 60 19 6 26 21 2 4 54 50 51 18 1 29 19 58 36 47 5 23 24 27 ...

result:

ok 90568 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 5864kb

input:

10742 15
14 10 12 13 1 13 9 3 9 3 2 1 5 2 10 5 12 2 3 6 8 9 12 12 9 11 5 1 14 10 10 5 4 5 7 6 14 6 4 3 10 11 13 1 13 13 2 9 5 10 14 8 2 2 13 10 7 12 8 9 11 7 7 7 2 1 9 12 6 12 3 3 12 1 6 12 3 11 6 3 6 13 1 11 2 9 6 8 8 2 6 10 15 14 10 3 13 5 13 1 14 13 14 5 9 11 8 2 9 7 13 6 12 15 4 12 11 6 4 13 11 ...

output:

2 15 14 5 10 5 9 12 9 12 6 10 3 6 15 3 14 6 12 7 1 9 14 14 9 4 3 10 2 15 15 3 8 3 11 7 2 7 8 12 15 4 5 10 5 5 6 9 3 15 2 1 6 6 5 15 11 14 1 9 4 11 11 11 6 10 9 14 7 14 12 12 14 10 7 14 12 4 7 12 7 5 10 4 6 9 7 1 1 6 7 15 13 2 15 12 5 3 5 10 2 5 2 3 9 4 1 6 9 11 5 7 14 13 8 14 4 7 8 5 4 4 5 12 10 1 7...

result:

ok 10742 numbers

Test #13:

score: 0
Accepted
time: 7ms
memory: 6068kb

input:

52651 22
3 19 10 19 16 6 16 22 2 9 3 21 22 3 7 17 13 11 12 11 22 1 8 10 1 9 22 15 11 12 20 20 13 22 18 17 2 9 2 3 22 7 2 10 3 8 10 22 7 8 21 4 1 9 18 22 1 2 22 16 8 6 16 14 6 6 11 8 14 6 2 19 2 21 8 13 8 16 19 19 19 8 16 3 6 7 16 10 3 20 14 22 19 10 17 8 7 20 16 1 15 17 17 7 22 12 8 17 5 5 6 16 7 5 ...

output:

6 18 5 18 21 14 21 2 17 19 6 1 2 6 13 16 20 12 8 12 2 10 4 5 10 19 2 11 12 8 3 3 20 2 22 16 17 19 17 6 2 13 17 5 6 4 5 2 13 4 1 7 10 19 22 2 10 17 2 21 4 14 21 15 14 14 12 4 15 14 17 18 17 1 4 20 4 21 18 18 18 4 21 6 14 13 21 5 6 3 15 2 18 5 16 4 13 3 21 10 11 16 16 13 2 8 4 16 9 9 14 21 13 9 13 5 3...

result:

ok 52651 numbers

Test #14:

score: 0
Accepted
time: 37ms
memory: 4480kb

input:

100000 60
7 36 14 6 39 10 52 2 51 22 4 53 22 36 15 28 9 26 55 41 18 30 21 38 44 28 12 48 42 43 8 42 15 11 35 14 39 10 42 13 43 13 3 35 19 38 5 49 21 47 2 48 8 9 28 51 29 13 37 8 60 59 41 41 21 48 15 2 3 48 27 8 59 19 36 21 30 45 50 3 18 43 19 3 54 39 22 10 39 37 34 47 54 48 17 6 31 27 23 32 30 38 22...

output:

7 36 14 6 39 10 52 2 51 22 4 53 22 36 15 28 9 26 55 41 18 30 21 38 44 28 12 48 42 43 8 42 15 11 35 14 39 10 42 13 43 13 3 35 19 38 5 49 21 47 2 48 8 9 28 51 29 13 37 8 60 59 41 41 21 48 15 2 3 48 27 8 59 19 36 21 30 45 50 3 18 43 19 3 54 39 22 10 39 37 34 47 54 48 17 6 31 27 23 32 30 38 22 3 18 36 4...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 49ms
memory: 4480kb

input:

100000 60
2 37 58 49 31 10 26 36 42 55 8 9 16 23 57 32 43 33 2 40 49 19 13 7 5 37 19 52 16 11 47 23 33 59 9 24 21 23 30 49 8 31 18 39 42 56 38 17 60 29 54 13 34 50 31 22 41 48 52 19 53 52 18 6 8 43 22 54 18 6 26 43 13 29 29 40 20 45 10 13 55 12 39 44 33 14 33 53 34 13 57 50 58 1 60 51 8 19 48 38 37 ...

output:

2 37 58 49 31 10 26 36 42 55 8 9 16 23 57 32 43 33 2 40 49 19 13 7 5 37 19 52 16 11 47 23 33 59 9 24 21 23 30 49 8 31 18 39 42 56 38 17 60 29 54 13 34 50 31 22 41 48 52 19 53 52 18 6 8 43 22 54 18 6 26 43 13 29 29 40 20 45 10 13 55 12 39 44 33 14 33 53 34 13 57 50 58 1 60 51 8 19 48 38 37 43 25 39 4...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 21ms
memory: 5864kb

input:

100000 60
22 35 12 9 49 16 23 30 16 23 19 38 31 34 24 51 25 53 59 52 32 59 20 52 23 46 44 5 59 59 54 41 30 40 60 60 48 23 47 14 16 58 24 17 51 15 4 58 37 45 60 45 48 36 44 7 2 44 35 38 16 2 60 32 58 20 37 39 50 36 43 44 51 14 29 36 22 54 26 22 15 20 12 53 19 44 9 57 55 19 47 10 24 58 10 38 13 32 23 ...

output:

58 35 4 29 1 55 14 21 55 14 16 27 20 59 28 23 42 11 43 24 47 43 38 24 14 8 25 17 43 43 41 22 21 7 5 5 48 14 2 26 55 37 28 39 23 30 18 37 12 50 5 50 48 60 25 15 51 25 35 27 55 51 5 47 37 38 12 3 57 60 53 25 23 26 36 60 58 41 34 58 30 38 4 11 16 25 29 44 10 16 2 45 28 37 45 27 40 47 14 60 17 54 58 59 ...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 22ms
memory: 4608kb

input:

100000 60
38 1 32 59 24 29 11 40 41 53 32 4 8 17 31 39 47 17 26 40 49 7 28 49 2 45 18 47 36 29 45 6 59 49 49 35 57 25 19 42 57 11 19 41 49 37 2 43 36 18 26 27 12 9 32 8 46 55 51 39 21 57 16 41 7 9 5 39 30 10 21 43 58 4 21 29 13 29 20 8 34 16 37 32 27 1 16 17 6 22 49 22 35 26 58 25 1 13 20 55 20 12 4...

output:

10 58 4 24 59 8 36 19 47 45 4 40 49 55 21 9 18 55 2 19 22 26 32 22 11 27 5 18 15 8 27 6 24 22 22 12 54 39 41 38 54 36 41 47 22 60 11 33 15 5 2 7 28 3 4 49 30 57 43 9 1 54 44 47 26 3 46 9 17 51 1 33 13 40 1 8 29 8 14 49 37 44 60 4 7 58 44 55 6 48 22 48 12 2 13 39 58 29 14 57 14 28 31 39 6 25 45 10 55...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 10ms
memory: 5988kb

input:

100000 60
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...

output:

7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 14ms
memory: 4608kb

input:

100000 60
18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18...

output:

18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 ...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 15ms
memory: 4608kb

input:

100000 60
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...

output:

30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 ...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 11ms
memory: 4608kb

input:

100000 60
53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53...

output:

29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 ...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 12ms
memory: 6116kb

input:

97200 60
28 14 56 52 33 17 17 28 42 22 12 44 51 43 57 8 15 45 4 11 21 7 38 19 47 13 36 47 38 50 57 29 11 11 39 15 37 29 24 38 9 36 4 59 25 4 46 46 23 2 37 18 42 59 52 45 9 30 50 36 6 32 15 57 8 41 10 4 8 31 3 60 9 31 7 59 12 17 22 51 45 49 20 50 37 24 26 28 3 57 13 45 54 5 33 29 32 57 21 2 3 48 53 1...

output:

1 2 3 4 5 6 6 1 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 23 21 26 13 27 18 18 28 15 29 27 30 21 31 25 17 32 33 17 34 34 35 36 29 37 7 32 4 16 31 38 26 25 39 40 15 13 14 41 42 17 14 43 44 45 31 43 20 32 9 6 8 11 16 46 47 26 29 30 48 1 44 13 24 16 49 50 5 27 40 13 19 36 44 51 52 24 53 52 ...

result:

ok 97200 numbers

Test #23:

score: 0
Accepted
time: 12ms
memory: 4608kb

input:

97200 60
41 58 55 30 40 42 6 29 30 25 51 45 23 17 21 10 12 44 10 26 41 14 24 42 27 8 60 55 49 5 17 59 41 12 39 15 54 52 32 43 59 6 11 10 26 60 24 6 40 25 22 33 43 56 29 15 5 10 52 57 59 9 15 29 59 58 17 36 41 58 11 60 20 35 49 2 60 59 60 3 51 55 45 44 11 24 13 22 41 31 24 23 4 36 4 27 32 27 28 56 50...

output:

1 2 3 4 5 6 7 8 4 9 10 11 12 13 14 15 16 17 15 18 1 19 20 6 21 22 23 3 24 25 13 26 1 16 27 28 29 30 31 32 26 7 33 15 18 23 20 7 5 9 34 35 32 36 8 28 25 15 30 37 26 38 28 8 26 2 13 39 1 2 33 23 40 41 24 42 23 26 23 43 10 3 11 17 33 20 44 34 1 45 20 12 46 39 46 21 31 21 47 36 48 41 37 48 8 49 38 43 50...

result:

ok 97200 numbers

Test #24:

score: 0
Accepted
time: 12ms
memory: 6212kb

input:

97200 60
21 37 1 23 13 12 28 8 41 60 2 56 25 21 41 39 4 27 53 58 55 35 52 51 50 23 27 37 7 7 53 34 56 51 13 56 21 5 53 25 37 2 57 4 9 3 57 58 14 13 2 16 16 58 10 37 20 21 48 41 37 52 31 3 1 50 28 51 20 59 17 38 11 42 47 31 51 46 13 52 11 35 17 34 10 2 33 41 3 54 41 53 21 60 16 43 17 25 40 49 43 11 3...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 1 9 14 15 16 17 18 19 20 21 22 23 4 16 2 24 24 17 25 12 22 5 12 1 26 17 13 2 11 27 15 28 29 27 18 30 5 11 31 31 18 32 2 33 1 34 9 2 21 35 29 3 23 7 22 33 36 37 38 39 40 41 35 22 42 5 21 39 20 37 25 32 11 43 9 29 44 9 17 1 10 31 45 37 13 46 47 45 39 43 14 18 30 24 9 48 8...

result:

ok 97200 numbers

Test #25:

score: 0
Accepted
time: 20ms
memory: 4608kb

input:

93551 60
34 49 31 2 60 13 44 48 48 40 24 4 1 38 1 12 48 14 59 17 30 1 19 37 48 23 9 54 56 15 22 47 56 55 40 44 12 38 27 16 5 16 25 23 56 8 15 23 19 58 32 30 30 36 6 9 24 4 51 31 48 49 47 56 5 7 32 23 5 45 30 33 52 33 7 12 15 46 51 2 17 16 16 40 22 52 17 13 6 30 27 32 55 17 53 39 28 21 40 52 37 45 19...

output:

1 3 4 15 5 2 10 6 6 9 8 7 14 16 14 12 6 11 13 20 17 14 19 18 6 22 25 24 28 21 30 23 28 27 9 10 12 16 26 39 29 39 34 22 28 31 21 22 19 32 35 17 17 33 42 25 8 7 36 4 6 3 23 28 29 37 35 22 29 41 17 40 43 40 37 12 21 38 36 15 20 39 39 9 30 43 20 2 42 17 26 35 27 20 47 49 54 45 9 43 18 41 19 11 11 38 35 ...

result:

ok 93551 numbers

Test #26:

score: 0
Accepted
time: 21ms
memory: 4480kb

input:

93602 60
52 30 49 38 25 36 20 18 49 59 44 33 27 36 48 23 23 43 4 56 40 14 37 17 49 18 50 7 35 42 55 31 51 19 32 31 19 29 35 26 27 34 15 35 47 51 43 17 4 19 15 47 32 8 17 11 22 34 5 48 13 24 5 25 58 14 23 32 4 28 56 32 51 5 34 31 43 39 7 48 4 1 18 24 50 11 29 39 54 6 50 21 7 53 18 33 15 10 51 43 10 1...

output:

6 1 2 3 4 5 7 12 2 18 8 10 15 5 13 14 14 21 16 9 19 11 17 20 2 12 23 26 22 24 28 29 30 25 27 29 25 34 22 32 15 37 33 22 38 30 21 20 16 25 33 38 27 35 20 31 36 37 39 13 40 46 39 4 42 11 14 27 16 44 9 27 30 39 37 29 21 59 26 13 16 41 12 46 23 31 34 59 45 55 23 47 26 58 12 10 33 43 30 21 43 12 55 55 17...

result:

ok 93602 numbers

Test #27:

score: 0
Accepted
time: 21ms
memory: 4608kb

input:

93567 60
16 9 27 36 29 39 40 56 56 58 41 47 54 1 29 44 16 10 4 4 14 20 56 32 31 59 49 13 23 25 3 32 37 36 28 5 18 10 51 30 30 52 57 2 4 5 57 56 53 31 11 1 38 16 23 28 37 1 30 24 49 6 38 33 26 2 45 32 8 34 39 8 16 11 33 22 19 55 35 32 48 52 28 20 28 55 39 5 7 9 25 42 47 13 40 39 42 21 28 38 15 5 39 4...

output:

2 5 3 1 4 7 6 10 10 8 9 12 15 20 4 11 2 13 16 16 18 19 10 22 14 17 24 30 31 32 29 22 26 1 23 25 27 13 28 21 21 36 40 37 16 25 40 10 34 14 44 20 33 2 31 23 26 20 21 35 24 42 33 51 45 37 39 22 38 43 7 38 2 44 51 41 46 48 55 22 52 36 23 19 23 48 7 25 47 5 32 57 12 30 6 7 57 53 23 33 59 25 7 39 40 43 30...

result:

ok 93567 numbers

Test #28:

score: 0
Accepted
time: 14ms
memory: 4480kb

input:

100000 60
45 4 17 19 45 44 14 20 13 26 19 58 6 1 43 60 31 40 34 16 16 49 30 44 24 21 6 16 18 42 2 39 23 57 10 23 12 30 14 2 4 9 31 18 19 49 2 51 16 57 53 48 54 50 35 44 33 24 36 31 46 34 3 41 59 45 24 35 28 40 12 28 47 55 58 28 10 52 24 1 58 32 53 54 20 55 53 32 30 15 52 11 6 23 25 40 48 47 11 11 15...

output:

1 2 3 4 1 5 6 7 8 9 4 10 11 12 13 14 15 16 17 18 18 19 20 5 21 29 11 18 22 23 24 25 26 27 28 26 30 20 6 24 2 31 15 22 4 19 24 32 18 27 33 34 35 36 37 5 38 21 39 15 40 17 41 42 43 1 21 37 44 16 30 44 45 46 10 44 28 47 21 12 10 48 33 35 7 46 33 48 20 49 47 50 11 26 51 16 34 45 50 50 49 31 47 52 22 1 5...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 13ms
memory: 4608kb

input:

100000 60
5 13 15 49 36 4 56 24 20 7 44 40 36 48 58 32 2 18 24 51 7 46 60 35 11 20 53 39 49 41 36 31 14 52 2 35 43 57 40 42 24 40 55 52 24 1 14 21 48 52 18 22 48 54 16 49 45 53 53 43 23 31 16 5 31 45 32 5 15 3 2 7 57 8 17 24 3 22 46 18 6 51 57 17 39 34 6 8 44 52 10 21 17 47 35 45 7 1 16 40 6 33 59 3...

output:

1 2 3 4 5 6 7 8 9 10 11 12 5 13 14 15 16 17 8 18 10 19 20 21 22 9 23 24 4 25 5 26 28 29 16 21 30 31 12 32 8 12 33 29 8 34 28 35 13 29 17 36 13 37 38 4 39 23 23 30 40 26 38 1 26 39 15 1 3 41 16 10 31 42 43 8 41 36 19 17 44 18 31 43 24 45 44 42 11 29 46 35 43 47 21 39 10 34 38 12 44 48 49 5 7 49 31 20...

result:

ok 100000 numbers

Test #30:

score: 0
Accepted
time: 20ms
memory: 6252kb

input:

100000 60
56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56...

output:

59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 ...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 11ms
memory: 6336kb

input:

100000 60
33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33...

output:

9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 ...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 13ms
memory: 6384kb

input:

99960 60
17 10 31 26 3 4 13 8 56 26 39 46 41 42 19 37 37 49 20 25 16 35 29 36 15 27 31 6 60 32 36 56 27 36 48 12 26 58 6 59 54 8 9 11 53 10 34 20 45 57 56 45 12 28 53 36 48 10 32 33 60 53 15 53 24 31 51 22 21 33 6 12 17 15 33 9 4 13 7 46 23 46 34 58 26 45 54 16 48 23 30 45 32 23 44 8 38 12 56 34 21 ...

output:

1 2 3 4 5 6 7 8 9 4 10 11 12 13 14 15 15 16 17 18 19 20 21 22 23 24 3 25 26 27 22 9 24 22 28 29 4 30 25 31 32 8 33 34 35 2 36 17 37 38 9 37 29 39 35 22 28 2 27 40 26 35 23 35 41 3 42 43 44 40 25 29 1 23 40 33 6 7 45 11 46 11 36 30 4 37 32 19 28 46 47 37 27 46 48 8 49 29 9 36 44 18 37 17 28 37 50 43 ...

result:

ok 99960 numbers

Test #33:

score: 0
Accepted
time: 12ms
memory: 4480kb

input:

99960 60
57 10 6 36 21 48 37 33 56 40 53 56 1 9 9 23 39 31 30 3 32 59 3 12 12 25 59 7 41 49 29 21 56 17 36 36 25 32 43 54 60 16 38 40 25 50 58 30 56 20 42 46 55 32 16 37 54 48 41 8 27 25 4 13 33 59 36 28 9 52 59 54 55 52 1 54 9 54 20 32 34 4 25 23 39 47 14 23 10 38 31 39 36 26 6 57 8 30 41 19 27 15 ...

output:

1 2 3 4 5 6 7 8 9 10 11 9 12 13 13 14 15 16 17 18 19 20 18 21 21 22 20 23 24 25 26 5 9 27 4 4 22 19 28 29 30 31 32 10 22 33 34 17 9 35 36 37 38 19 31 7 29 6 24 39 40 22 41 42 8 20 4 43 13 44 20 29 38 44 12 29 13 29 35 19 45 41 22 14 15 46 47 14 2 32 16 15 4 48 3 1 39 17 24 49 40 50 7 2 51 44 12 21 2...

result:

ok 99960 numbers

Test #34:

score: 0
Accepted
time: 34ms
memory: 4480kb

input:

100000 60
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 ...

result:

ok 100000 numbers