QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90345 | #6116. Changing the Sequences | HOLIC# | WA | 2ms | 3772kb | C++20 | 3.6kb | 2023-03-22 19:00:00 | 2023-03-22 19:00:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 65;
int n, m, pas;
namespace KM{
int match[N], vis[N], pre[N];
int upd[N], delta, la[N], lb[N], w[N][N];
void bfs(int s) {
int x, y = 0, yy;
memset(pre, 0, sizeof(pre));
for(int i = 1; i <= n; i ++) upd[i] = 1e9;
match[y] = s;
while(true) {
x = match[y], delta = 1e9, vis[y] = 1;
for(int i = 1; i <= n; i ++) {
if(vis[i]) continue;
if(upd[i] > la[x] + lb[i] - w[x][i]) {
upd[i] = la[x] + lb[i] - w[x][i];
pre[i] = y;
}
if(upd[i] < delta) delta = upd[i], yy = i;
}
for(int i = 0; i <= n; i ++) {
if(vis[i]) {
la[match[i]] -= delta;
lb[i] += delta;
} else upd[i] -= delta;
}
y = yy;
if(!match[y]) break;
}
while(y) {
match[y] = match[pre[y]];
y = pre[y];
}
}
void build() {
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
w[i][j] = 0;
}
int KM() {
for(int i = 1; i <= n; i ++) la[i] = 0;
for(int i = 1; i <= n; i ++) match[i] = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
la[i] = max(la[i], w[i][j]);
for(int i = 1; i <= n; i ++) {
memset(vis, 0, sizeof(vis));
bfs(i);
}
int ans = 0;
for(int i = 1; i <= n ; i ++) ans += w[match[i]][i];
return ans;
}
}
int a[100010], b[100010], w[61][61];
int id[61], pos[61], st, ed;
inline bool kkk(int x, int y){
return pos[x] < pos[y];
}
int match[N], to[N];
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i) pos[i] = n + 1, id[i] = i;
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = n; i; --i) pos[a[i]] = i;
for(int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for(int i = 1; i <= n; ++i) ++w[a[i]][b[i]];
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= m; ++j) KM::w[i][j] = w[i][j];
int ans = KM::KM();
// cout << ans <<endl;
sort(id + 1, id + m + 1, kkk);
for(int i = 1; i <= m; ++i){
int x = id[i];
auto solve = [&]() {
KM::build();
for(int j = i + 1; j <= m; j ++) {
for(int k = 1; k <= m; k ++) {
if(match[k]) continue;
//MCFC::add(id[j], k + m, 1, w[id[j]][k]), MCFC::add(k + m, id[j], 0, -w[id[j]][k]);
KM::w[id[j]][k] = w[id[j]][k];
}
}
};
int val = 0;
for(int j = 1; j <= m; ++j){
if(match[j]) continue;
// cout << x << " " << val << " " << j << endl;
solve();
//MCFC::add(x, j + m, 1, w[x][j]);
//MCFC::add(j + m, x, 0, -w[x][j]);
KM::w[x][j] = w[x][j];
val = KM::KM();
// cout << val << " " << ans << endl;
if(val + pas == ans) {
to[x] = j;
match[j] = 1;
pas += w[x][j];
break;
}
}
// cout<< x << "!!!" << endl;
}
for(int i = 1; i <= n; i ++) printf("%d ", to[a[i]]);
printf("\n");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
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: 0ms
memory: 3572kb
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: 0ms
memory: 3760kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3772kb
input:
1 60 60 60
output:
1
result:
wrong answer 1st numbers differ - expected: '60', found: '1'