QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90343 | #6116. Changing the Sequences | HOLIC# | RE | 2ms | 3636kb | C++20 | 3.8kb | 2023-03-22 18:52:10 | 2023-03-22 18:52:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 201, M = 4000;
namespace MCFC{
bool vis[N];
const int inf = 0x3f3f3f3f;
int s, t, incf[N], pre[N], d[N], head[N], nexts[M], edge[M], ver[M], cost[M], cnt = 1;
void add(int x, int y, int z, int c){
ver[++ cnt] = y, nexts[cnt] = head[x], head[x] = cnt, edge[cnt] = z, cost[cnt] = c;
}
void clear() {
for(int i = 1; i <= t; i ++) head[i] = 0;
cnt = 1;
}
bool spfa(){
queue<int> q;
memset(d, ~0x3f, sizeof(d));
// cout << d[0];
//exit(0);
q.push(s); d[s] = 0; incf[s] = inf;
while(!q.empty()){
int x = q.front(); q.pop();
// cout << x << " " << d[x] <<endl;
vis[x] = 0;
for(int i = head[x]; i; i = nexts[i]){
int v = ver[i];
if(edge[i] && d[v] < d[x] + cost[i]){
d[v] = d[x] + cost[i];
incf[v] = min(incf[x], edge[i]);
pre[v] = i;
if(vis[v]) continue;
vis[v] = 1;
q.push(v);
}
}
}
return d[t] != -1061109568;
}
int EK() {
int flow = 0, cost = 0;
while(spfa()) {
// cout << "!!!" << endl;
int ff = incf[t];
flow += ff; cost += ff * d[t];
for(int i = t; i != s; i = ver[pre[i] ^ 1]){
edge[pre[i]] -= ff;
edge[pre[i] ^ 1] += ff;
}
}
return cost;
}
}
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(){
int n, m, pas = 0;
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]];
MCFC::s = m + m + 1, MCFC::t = m + m + 2;
for(int i = 1; i <= m; ++i){
MCFC::add(MCFC::s, i, 1, 0), MCFC::add(i, MCFC::s, 0, 0);
MCFC::add(i + m, MCFC::t, 1, 0), MCFC::add(MCFC::t, i + m, 0, 0);
}
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= m; ++j) MCFC::add(i, j + m, 1, w[i][j]), MCFC::add(j + m, i, 0, -w[i][j]);
int ans = MCFC::EK();
// cout << ans <<endl;
sort(id + 1, id + m + 1, kkk);
for(int i = 1; i <= m; ++i){
int x = id[i];
auto solve = [&]() {
MCFC::clear();
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]);
}
}
for(int j = 1; j <= m; j ++)
MCFC::add(MCFC::s, j, 1, 0), MCFC::add(j, MCFC::s, 0, 0),
MCFC::add(j + m, MCFC::t, 1, 0), MCFC::add(MCFC::t, j + m, 0, 0);
};
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]);
val = MCFC::EK();
// 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: 3576kb
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: 2ms
memory: 3636kb
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: 3528kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Runtime Error
input:
1 60 60 60