QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90345#6116. Changing the SequencesHOLIC#WA 2ms3772kbC++203.6kb2023-03-22 19:00:002023-03-22 19:00:01

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:00:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3772kb
  • [2023-03-22 19:00:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 65;
int n, m, pas;
namespace KM{
    int match[N], vis[N], pre[N];
    int 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] = 1e9;
        match[y] = s;
        while(true) {
            x = match[y], delta = 1e9, 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;
    }
    int KM() {
        for(int i = 1; i <= n; i ++) la[i] = 0;
        for(int i = 1; i <= n; i ++) match[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);
            }
            int 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", &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]];
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= m; ++j) KM::w[i][j] = w[i][j];
        int ans = KM::KM();
        // cout << ans <<endl;
        sort(id + 1, id + m + 1, kkk);
        for(int i = 1; i <= m; ++i){
            int x = id[i];
            auto solve = [&]() {
                KM::build();
                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]);
                        KM::w[id[j]][k] = w[id[j]][k];
                    }
                }
            };
            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]);
                KM::w[x][j] = w[x][j];
                val = KM::KM();
                // 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3536kb

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: 0ms
memory: 3572kb

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: 3760kb

input:

1 1
1
1

output:

1 

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3772kb

input:

1 60
60
60

output:

1 

result:

wrong answer 1st numbers differ - expected: '60', found: '1'