47422023-03-31 10:40:45Albertstein99Óvodacpp17Futási hiba 16/50118ms63568 KiB
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

int main(){
    int N, K;
    cin >> N >> K;
    vector <int> M(K + 1);
    for(int i = 1; i <= K; i++)
        cin >> M[i];
    vector <int> S(N + 1);
    for(int i = 1; i <= N;i++)
        cin >> S[i];
    vector <int> T(N + 1);
    for(int i = 1; i <= N;i++)
        cin >> T[i];
    vvpii R(K + 1);
    for(int i = 1; i <= N; i++)
        R[S[i]].push_back({T[i], i});
    for(auto &x : R)
        sort(x.begin(), x.end());
    vector <int> extras;
    for(int i = 1; i <= K; i++)
        for(int j = R[i].size(); j < M[i]; j++)
            extras.push_back(i);
    unique(extras.begin(), extras.end());
    vector <int> P(N + 1);
    int p = 0;
    for(int i = 1; i <= K; i++){
        int num = max((signed long long)(R[i].size() - M[i]), 0ll);
        for(int j = 0; j < num; j++)
            P[R[i][j].second] = extras[p++];
        for(int j = num; j < R[i].size(); j++)
            P[R[i][j].second] = i;
    }
    vvpii F(K + 1);
    for(int i = 1; i <= N; i++){
        F[P[i]].push_back({T[i], i});
    }
    for(auto &x : F){
        sort(x.begin(), x.end(), greater<pii>());
    }
    vector <int> needs;
    for(int i = 1; i <= K; i++)
        if(F[i].empty())
            needs.push_back(i);
    vpii usable;
    for(int i = 1; i <= K; i++){
        for(int j = 1; j <= F.size(); j++)
            usable.push_back(F[i][j]);
    }
    sort(usable.begin(), usable.end());
    for(int i = 0; i < needs.size(); i++){
        P[usable[i].second] = needs[i];
    }
    int cry = 0;
    for(int i = 1; i <= N; i++){
        if(S[i] != P[i])
            cry += T[i];
    }
    cout << cry << "\n";
    for(int i = 1; i <= N; i++)
        cout << P[i] << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base16/50
1Elfogadva0/03ms1812 KiB
2Futási hiba0/07ms3856 KiB
3Elfogadva2/23ms2212 KiB
4Futási hiba0/23ms2524 KiB
5Részben helyes1/23ms2644 KiB
6Elfogadva2/22ms2724 KiB
7Futási hiba0/23ms3096 KiB
8Elfogadva2/22ms2968 KiB
9Elfogadva2/23ms3012 KiB
10Elfogadva2/23ms3224 KiB
11Elfogadva2/22ms3340 KiB
12Részben helyes1/22ms3304 KiB
13Futási hiba0/24ms4232 KiB
14Részben helyes1/34ms3736 KiB
15Futási hiba0/348ms63568 KiB
16Futási hiba0/337ms25552 KiB
17Futási hiba0/371ms63320 KiB
18Futási hiba0/364ms18804 KiB
19Futási hiba0/394ms63140 KiB
20Részben helyes1/390ms13224 KiB
21Futási hiba0/3114ms63148 KiB
22Futási hiba0/4118ms29996 KiB