QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90342 | #6116. Changing the Sequences | HOLIC# | WA | 2ms | 3676kb | C++20 | 3.8kb | 2023-03-22 18:51:34 | 2023-03-22 18:51:37 |
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: 0
Wrong Answer
time: 2ms
memory: 3676kb
input:
4 3 2 2 3 3 2 2 2 2
output:
2 1 1 2 2
result:
wrong answer 1st numbers differ - expected: '1', found: '2'