AtCoder-Solutions/contest/contest1/2.cpp at main · LSUDOKO/AtCoder-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// #include <bits/stdc++.h>
// using namespace std;

// int main() {
//     int n;
//     cin >> n;
//     vector<int> ans(n);
//     map<int,int> frq;
//     vector<int> rem;
//     vector<int> pu;
//     bool check = true;

//     for (int i = 0; i < n; i++) {
//         cin >> ans[i];
//         frq[ans[i]]++;
//         if (ans[i] != -1) {
//             pu.push_back(ans[i]);
//         }
//     }

//     for (int i = 1; i <= n; i++) {
//         if (find(pu.begin(), pu.end(), i) == pu.end()) {
//             rem.push_back(i);
//         }
//     }

//     for (auto p : frq) {
//         if (p.first != -1 && p.second > 1) {
//             check = false;
//         }
//     }

//     if (check) {
//         int j = 0;
//         for (int i = 0; i < n; i++) {
//             if (ans[i] == -1) {
//                 ans[i] = rem[j++];
//             }
//         }
//         cout << "Yes"<<endl;
//         for (int i = 0; i < n; i++) {
//             cout << ans[i] << " ";
//         }
//         cout <<endl;
//     } else {
//         cout << "No"<<endl;
//     }
// }


// optimized sol
#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    set<int> used;
    for(int i = 0; i < N; i++) {
        if(A[i] != -1) {
            if(used.count(A[i])) {
                cout << "No" << endl;
                return 0;
            }
            used.insert(A[i]);
        }
    }
    vector<int> remaining;
    for(int x = 1; x <= N; x++) {
        if(!used.count(x)) {
            remaining.push_back(x);
        }
    }
    vector<int> P = A;
    int j = 0;
    for(int i = 0; i < N; i++) {
        if(P[i] == -1) {
            P[i] = remaining[j];
            j++;
        }
    }
    cout << "Yes" << endl;
    for(int i = 0; i < N; i++) {
        if(i > 0) cout << " ";
        cout << P[i];
    }
    cout << endl;
    return 0;
}