QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90661 | #6116. Changing the Sequences | qgoi_official# | WA | 5ms | 3808kb | C++14 | 1.5kb | 2023-03-24 15:56:16 | 2023-03-24 15:56:19 |
Judging History
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;
}
詳細信息
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'