QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90347#6116. Changing the SequencesHOLIC#TL 0ms0kbC++203.2kb2023-03-22 19:04:362023-03-22 19:04: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 19:04:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-03-22 19:04:36]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4 3
2 2 3 3
2 2 2 2

output:


result: