QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90342#6116. Changing the SequencesHOLIC#WA 2ms3676kbC++203.8kb2023-03-22 18:51:342023-03-22 18:51:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-22 18:51:37]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3676kb
  • [2023-03-22 18:51:34]
  • 提交

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'