QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90661#6116. Changing the Sequencesqgoi_official#WA 5ms3808kbC++141.5kb2023-03-24 15:56:162023-03-24 15:56:19

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-24 15:56:19]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3808kb
  • [2023-03-24 15:56:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, a[N], b[N], p[65], cnt[65][65], ord[65], vis[65], top = 0;
int ansp[N], ans = 0;

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f;
}

mt19937 rnd(time(0));

inline int chk() {
	int res = 0;
	for (int i = 1; i <= m; ++i) res += cnt[i][p[i]];
	if (res > ans) {
		ans = res;
		for (int i = 1; i <= m; ++i) ansp[i] = p[i];
		return -1;
	}
	if (res < ans) return res;
	for (int i = 1; i <= top; ++i) {
		if (p[ord[i]] == ansp[ord[i]]) continue;
		if (p[ord[i]] < ansp[ord[i]]) {
			for (int j = 1; j <= m; ++j) ansp[j] = p[j];
			return -1;
		}
		return res;
	} return -1;
}

inline void SA() {
	for (double t = 5000; t > 1e-6; t = t * 0.9112) {
		int x = rnd() % m + 1, y = rnd() % m + 1;
		swap(p[x], p[y]); int re = chk();
		if (x != -1) {
			if (exp((re - ans) / t) < (double)rand() / (double)RAND_MAX) swap(p[x], p[y]);
		}
	}
}

int main() {
//	freopen("C.in", "r", stdin);
	clock_t beg =  clock();
	n = read(); m = read();
	for (int i = 1; i <= n; ++i) a[i] = read(), ansp[i] = p[i] = i;
	for (int i = 1; i <= n; ++i)
		if (!vis[a[i]]) ord[++top] = a[i], vis[a[i]] = 1;
	for (int i = 1; i <= n; ++i) b[i] = read(), ++cnt[a[i]][b[i]], ans += (a[i] == b[i]);
	while (clock() - beg < 1900) SA();
	for (int i = 1; i <= n; ++i) printf("%d ", ansp[a[i]]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3736kb

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: 4ms
memory: 3772kb

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: 5ms
memory: 3808kb

input:

1 1
1
1

output:

1 

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 3800kb

input:

1 60
60
60

output:

0 

result:

wrong answer 1st numbers differ - expected: '60', found: '0'