Cops and Robbers

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int main(){
    6    ios::sync_with_stdio(0);
    7    cin.tie(0);
    8    int n;
    9    cin >> n;
    10    vector<int> v(n + 1);
    11    for(int i = 1; i <= n; i++){
    12        cin >> v[i];
    13    }
    14    vector<int> first_occur(n + 1);
    15    for(int i = 1; i < v.size(); i++){
    16        int f = v[i];
    17        if(first_occur[f] == 0){
    18            first_occur[f] = i;
    19        }
    20    }
    21    vector<int> inv(n + 1);
    22    for(int i = 1; i < v.size(); i++){
    23        int d = first_occur[i];
    24        if(d != 0){
    25            inv[d] = i;
    26        }
    27    }
    28    vector<int> order;
    29    for(int i = 1; i <= n; i++){
    30        if(inv[i] != 0){
    31            order.push_back(inv[i]);
    32        }
    33    }
    34    //one day is guarded every day
    35    if(order.size() < 2){
    36        cout << -1 << '\n';
    37        exit(0);
    38    }
    39    vector<int> ans(n + 1); 
    40    for(int i = 0; i < order.size(); i++){
    41        int cur = order[i];
    42        int prev = order[(i + order.size() - 1) % order.size()];
    43        int day = first_occur[cur];
    44        ans[day] = prev;
    45    }
    46    vector<bool> used_bank(n + 1), used_day(n + 1);
    47    for(int bank : order){
    48        used_bank[bank] = true;
    49        used_day[first_occur[bank]] = true;
    50    }
    51    //assign position for banks that the gaurd never gaurded 
    52    vector<int> days, banks;
    53    for(int i = 1; i <= n; i++){
    54        if(!used_bank[i]) banks.push_back(i);
    55    }
    56    for(int i = 1; i <= n; i++){
    57        if(!used_day[i]) days.push_back(i);
    58    }
    59    for(int i = 0; i < days.size(); i++){
    60        ans[days[i]] = banks[i];
    61    }   
    62    for(int i = 1; i < ans.size(); i++){
    63         cout << ans[i] << (i == ans.size() - 1 ? "\n" : " ");
    64    }
    65    return 0;
    66}