QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90347 | #6116. Changing the Sequences | HOLIC# | TL | 0ms | 0kb | C++20 | 3.2kb | 2023-03-22 19:04:36 | 2023-03-22 19:04:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 65;
int n, m, pas;
#define ll long long
namespace KM{
int match[N], vis[N], pre[N];
ll 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] = 1e18;
match[y] = s;
while(true) {
x = match[y], delta = 1e18, 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;
}
ll KM() {
for(int i = 1; i <= n; i ++) la[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);
}
ll 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", &m, &n);
for(int i = 1; i <= n; ++i) pos[i] = m + 1, id[i] = i;
for(int i = 1; i <= m; ++i) scanf("%d", &a[i]);
for(int i = m; i; --i) pos[a[i]] = i;
for(int i = 1; i <= m; ++i) scanf("%d", &b[i]);
for(int i = 1; i <= m; ++i) ++w[a[i]][b[i]];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) KM::w[i][j] = w[i][j];
int ans = KM::KM();
sort(id + 1, id + n + 1, kkk);
for(int i = 1; i <= n; ++i){
int x = id[i];
auto solve = [&]() {
KM::build();
for(int j = i + 1; j <= n; j ++) {
for(int k = 1; k <= n; k ++) {
if(match[k]) continue;
KM::w[id[j]][k] = w[id[j]][k];
}
}
};
int val = 0;
for(int j = 1; j <= n; ++j){
if(match[j]) continue;
solve();;
KM::w[x][j] = w[x][j];
val = KM::KM();
if(val + pas == ans) {
to[x] = j;
match[j] = 1;
pas += w[x][j];
break;
}
}
// cout<< x << "!!!" << endl;
}
for(int i = 1; i <= m; i ++) printf("%d ", to[a[i]]);
printf("\n");
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
4 3 2 2 3 3 2 2 2 2