02-05 18:01 羽丘女子学园 C++ 发布于福建

关注

牛客寒假营第二场题解

签到：A

easy：B、I

mid：E、F、H

hard：J

防AK：C、D、G

shit：B、G

前言

好难！

好难好难！！

好难好难好难好难！！！！

好难好难好难好难好难好难好难好难！！！！！！！！

B很坑，WA了4发才过，H一开始数据错了，爆了long long，但是验题已经过了十多个，我assert了一下发现果然爆了，于是将数据规模减小了。

E题不同的人差距很大，电波对上的话，不到五分钟就能过。

前七题和后三题完全不是同一个难度的，割裂有点大。G还有 $2 \times 10^6$ 的平衡树，非常阴间。

A 比赛安排

签到

由于连续三个不同，那么意味着一定是 $1\ 2\ 3\ 1\ 2\ 3$ 循环，最后可以多出 $1$ 或者 $1\ 2$ 。

整合一下就是排序后最多的数与最少的数差值不超过 $1$ 。

时间复杂度： $O(1)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        array<int, 3> a;
        for(auto &i : a){
            cin >> i;
        }
        ranges::sort(a);
        if(a[2] - a[0] <= 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

B NCPC

排序、贪心

如果最大的数的个数为奇数：

那么无论如何最后一定会剩一个最大的数，因此最大的数都可以获胜，因为一定会需要将最大的数两两消除，最后剩一个无法消除。

如果最大的数的个数为偶数：

最大的数最终一定会两两消去，除了最大的数都可以获胜，我们只要用一个最大的干掉所有小的，只留一个想让他赢的，最后将最大的数两两消去即可。

时间复杂度： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
   int T;
   cin >> T;
   while(T--){
       int n;
       cin >> n;
       map<int, vector<int>> mp;
       string s(n, '0');
       for(int i = 0; i < n; i++){
           int x;
           cin >> x;
           mp[x].push_back(i);
       }
       auto &[x, y] = *prev(mp.end());
       int t = 1;
       if(y.size() % 2 == 0){
           t = -1;
           s = string(n, '1');
       }
       for(auto &i : y){
           s[i] += t;
       }
       cout << s << endl;
   }
}

C 炮火轰炸

搜索、二分

如果值域在 $1000$ 以内，我们可以直接暴力染色，暴力染色实际上最终会将雷的外侧空格包围起来，我们能不能快速将雷的外侧包围起来呢？

由于雷的数量为 $n$ ，因此我们每次沿着雷的外侧走，就可以用不超过 $8n$ 个标记为 $0$ 的空格将雷围起来。（只标记周围有雷的空格）

那么每个雷内侧剩余的没被标记的空格就在炮火圈中，我们可以用类似上面的方法用不超过 $8n$ 个标记为 $1$ 的空格将炮火圈围起来。

对于一个雷我们怎么知道雷的外侧空格和内侧空格是哪个呢？

我们按照从上到下，从左到右的顺序枚举，那么一个连通块中的第一个雷一定会在最左上方被枚举到，第一个雷的左上方一定是雷的外侧空格，从这个点开始搜索就可以绕完这整个连通块的外侧了。

反之，任意一个雷的右方、下方、右下方空格没有被搜索过，说明这个位置一定是内侧空格，在炮火圈中。

注意：如果一个雷已经在炮火圈中，则需要将这个雷删除。

现在每次查询只要知道 $(x, y)$ 在不在炮火圈内即可，如何查询呢？

由于有一些点标记成了 $0$ 或 $1$ ：

如果 $(x, y)$ 标记为 $0$ ，它不在炮火圈里；

如果 $(x, y)$ 标记为 $1$ ，它在炮火圈里；

如果 $(x, y)$ 上下左右四个方向出现的第一个被标记的空格都是 $1$ ，则它在炮火圈里；（可以使用二分）

否则说明它不在炮火圈里。

时间复杂度： $O(8n \times log8n + q \times log8n)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, q;
    cin >> n >> q;
    vector st(1e6 + 2, set<int>());
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        st[x].insert(y);
    }
    vector<array<int, 2>> d = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    vector mp(1e6 + 2, map<int, int>());
    vector mx(1e6 + 2, set<int>()), my = mx;
    auto in = [&](int x, int y){
        auto itx = mx[x].lower_bound(y);
        auto ity = my[y].lower_bound(x);
        if(itx == mx[x].end() || ity == my[y].end()) return 0;
        return min(mp[x][*itx], mp[*ity][y]);
    };
    auto dfs = [&](this auto &&dfs, int x, int y, int cnt){
        mp[x][y] = cnt;
        mx[x].insert(y);
        my[y].insert(x);
        for(auto &[dx, dy] : d){
            int xx = x + dx;
            int yy = y + dy;
            if(xx < 0 || yy < 0) continue;
            if(st[xx].count(yy)) continue;
            if(mp[xx].count(yy)) continue;
            int tag = 0;
            for(int dx = -1; dx <= 1; dx++){
                for(int dy = -1; dy <= 1; dy++){
                    if(xx + dx >= 0) tag |= st[xx + dx].count(yy + dy);
                }
            }
            if(tag) dfs(xx, yy, cnt);
        }
    };
    for(int x = 1; x <= 1e6; x++){
        for(auto &y : st[x]){
            if(in(x, y)) continue;
            for(int dx = -1; dx <= 1; dx++){
                for(int dy = -1; dy <= 1; dy++){
                    int xx = x + dx;
                    int yy = y + dy;
                    if(xx < 0 || yy < 0) continue;
                    if(st[xx].count(yy)) continue;
                    if(mp[xx].count(yy)) continue;
                    if(min(dx, dy) >= 0) dfs(dfs, xx, yy, 1);
                    else dfs(xx, yy, 0);
                }
            }
        }
    }
    while(q--){
        int x, y;
        cin >> x >> y;
        if(in(x, y)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

D 数字积木

树形DP、数学

实际上权值就是 $mex$ 。计算所有连通块的 $mex$ ，可以转化成枚举 $x$ ，求有多少个连通块的 $mex$ 为 $x$ （有多少个连通块包含 $[0, x - 1]$ 且不包含 $x$ ）

然后再进行一步转化，将 $mex$ 的贡献拆分：枚举 $x$ ，求有多少个连通块包含 $[0,x]$ 。

包含 $[0,x]$ 的连通块中，有些包含 $x + 1$ 怎么办？实际上这不重要，因为这些连通块一定会在枚举 $x + 1$ 的时候再次被计算一次。

那么现在问题就转化成了求连通块个数，对于一棵有根树的连通块个数可以用 DP 解决。

定义 $dp_u$ 为以 $u$ 为根的子树能产生多少个包含点 $u$ 的连通块， $dp_u = \prod dp_v + 1$ 。

以权值位 $0$ 的点为根就可以解决包含 $0$ 的连通块个数了

枚举 $x$ 时，显然从 $x$ 到根的链都必须存在，而其他点则可以选或不选，因此我们可以从 $x$ 往根走，去除链对连通块数量的贡献。

在本题之前的版本中，数据保证了不会有 $(dp_u + 1) \% (10^9 + 7) = 0$ 的情况，因此可以直接使用乘除法。但是在昨天去掉了这个限制，因此现在我们不可以使用除法，需要手动记录 $0$ 因子或者使用类似换根 DP 的前后缀进行优化。

时间复杂度： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

template<const int M = 1e9 + 7>
struct MInt {
    using LL = long long;
    int x;
    MInt(int x = 0) : x(norm(x)) {}
    MInt(LL x) : x(norm(x % M)) {}
    inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
    inline MInt ksm(MInt x, LL y) const {return x ^= y;}
    inline int val() const {return x;}
    inline MInt operator - () const {return MInt(norm(M - x));}
    inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
    inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
    inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
    inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
    inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
    inline MInt& operator ^= (LL y){
        LL ans = 1;
        while(y){
            if(y & 1) ans = ans * x % M;
            x = LL(x) * x % M;
            y >>= 1;
        }
        x = ans;
        return *this;
    }
    inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
    inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
    inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
    inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
    inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
    inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
    inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt;

int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1), in(n);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        in[a[i]] = i;
    }
    vector ve(n + 1, vector<int>());
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    struct SafeProd {
        int zero = 0;
        Z prod = 1;
        void mul(const Z& x) {if (x.val() == 0) zero++; else prod *= x;}
        void div(const Z& x) {if (x.val() == 0) zero--; else prod /= x;}
        Z val() const {return zero ? Z(0) : prod;}
    };
    vector<int> fa(n + 1), tag(n + 1);
    vector dp(n + 1, SafeProd());
    auto dfs = [&](auto &dfs, int u) -> void{
        if(fa[u]) ve[u].erase(ranges::find(ve[u], fa[u]));
        for(auto &v : ve[u]){
            fa[v] = u;
            dfs(dfs, v);
            dp[u].mul(dp[v].val() + 1);
        }
    };
    int root = in[0];
    dfs(dfs, root);
    vector<int> st(n + 1);
    auto sum = dp[root];
    Z ans = sum.val();
    st[root] = 1;
    for(int i = 1; i < n; i++){
        int u = in[i];
        while(!st[u]){
            st[u] = 1;
            sum.div(dp[u].val() + 1);
            for(auto &v : ve[u]){
                sum.mul(dp[v].val() + 1);
            }
            u = fa[u];
        }
        ans += sum.val();
    }
    cout << ans << endl;
}

E 01矩阵

构造

题目给出了答案为 $2$ 的构造

类推一下答案为 $3, 4, 5$ 的构造：

然后就好了。

时间复杂度： $O(n^2)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << "10"[min(i, j) & 1];
        }
        cout << endl;
    }
}

F x?y?n!

数论、位运算

观察样例可以得出一个猜测： $x \oplus y = gcd(x, y) = n$ 我们令 $x$ 是 $n$ 的倍数， $y = x + n$ ，此时可以确保 $gcd(x, y) = n$ ，如何在上述要求下满足 $x \oplus y = n$ 呢？

将 $x \oplus y = n$ 移项可以得到 $y = x \oplus n$ ，现在需要同时满足 $y = x + n，y = x \oplus n$ 这两个式子，继续展开可以得到：

$y = x + n = (x | n) + (x \& n)$

$y = x \oplus n = (x | n) - (x \& n)$

因此只要满足 $x \& n = 0$ 即可，现在我们需要构造 $x$ 是 $n$ 的倍数，且 $x \& n = 0$ 。

左移操作实际上相当于一个数乘 $2$ ，令 $x = n << 32$ ，就相当于 $x = n \times 2^{32}$ ， $x$ 一定是 $n$ 的倍数，且满足 $x \& n = 0$ ，因此我们得出了 $x$ ， $y = x + n$ 就得到了 $y$ 。

时间复杂度： $O(1)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        auto n = 0ll;
        cin >> n;
        cout << format("{} {}", n << 32, n << 32 | n) << endl;
    }
}

G 宝藏拾取

数据结构、平衡树

将问题转化一下就是每次对 $[1, i - 1]$ 的前缀中大于等于 $a_i$ 的数进行 $+a_i$ 操作，这东西在线段树上不容易维护，因为需要加 $a_i$ 的那些数是不连续的。

如果我们从前往后一个个数字加入，前缀操作实际上就变成了全局操作，如果序列有序，找到第一个大于等于 $a_i$ 的位置后就变成了一个区间 $+a_i$ 的操作。如果我们可以维护一个有序的序列，每次插入一个数字后还是维持有序，并且能找到第一个大于等于 $a_i$ 的位置……

这不就是 set 吗？现在似乎还差区间操作。回忆一下 set的本质，实际上是一棵平衡树，我们只需要手写一棵平衡树实现 set 的 insert 、 lower_bound ，最后用类似线段树懒标记的方法实现区间加即可。

时间复杂度： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

template<typename T, const int M = 7>
class Splay{
public:
    vector<array<T, M>> tr;
    Splay(){
        tr.push_back({});
        tr[0][3] = -9e18;
    }

    inline void addSon(int u, int t, T x, int idx){
        tr[u][t] = tr.size();
        tr.push_back({0, 0, u, x, 1, 0, idx});
    }

    inline void pushup(int u){
        tr[u][4] = 1;
        if(lson(u)) tr[u][4] += tr[lson(u)][4];
        if(rson(u)) tr[u][4] += tr[rson(u)][4];
    }

    inline void pushdown(int u){
        if(lson(u)){
            val(lson(u)) += tag(u);
            tag(lson(u)) += tag(u);
        }
        if(rson(u)){
            val(rson(u)) += tag(u);
            tag(rson(u)) += tag(u);
        }
        tag(u) = 0;
    }
    
    void rotate(int u){
        int t = lor(u);
        int fa = tr[u][2];
        int gf = tr[fa][2];
        int os = tr[u][t ^ 1];
        pushdown(u);
        swap(tr[gf][lor(fa)], tr[fa][t]);
        swap(tr[fa][t], tr[u][t ^ 1]);
        swap(tr[u][2], tr[fa][2]);
        if(os) swap(tr[fa][2], tr[os][2]);
        else tr[fa][2] = u;
        pushup(fa);
        pushup(u);
    }

    int splay(int u, int v){
        while(tr[u][2] != v){
            int fa = tr[u][2];
            int gf = tr[fa][2];
            if(gf != v){
                if(lor(u) == lor(fa)) rotate(fa);
                else rotate(u);
            }
            rotate(u);
        }
        return u;
    }

    void update(int x){
        int u = 0;
        while(1){
            pushdown(u);
            int t = x >= val(u);
            if(val(u) >= x) val(u) += x;
            if(!t){
                if(rson(u)){
                    tag(rson(u)) += x;
                    val(rson(u)) += x;
                }
            }
            if(!tr[u][t]) break;
            u = tr[u][t];
        }
        splay(u, 0);
    }

    void insert(T x, int idx){
        int u = 0, t = 0;
        while(1){
            t = x >= val(u);
            if(!tr[u][t]) break;
            u = tr[u][t];
        }
        addSon(u, t, x, idx);
        splay(tr.size() - 1, 0);
    }

    vector<array<T, 2>> toVector(int x = 0){
        vector<array<T, 2>> ans;
        auto dfs = [&](auto &dfs, int u) -> void{
            pushdown(u);
            if(tr[u][0]) dfs(dfs, tr[u][0]);
            ans.push_back({tr[u][3], tr[u][6]});
            if(tr[u][1]) dfs(dfs, tr[u][1]);
        };
        dfs(dfs, tr[0][x]);
        return ans;
    }

    inline int lor(int u){
        return rson(fa(u)) == u;
    }

    inline T& lson(int u){
        return tr[u][0];
    }

    inline T& rson(int u){
        return tr[u][1];
    }

    inline T& fa(int u){
        return tr[u][2];
    }

    inline T& val(int u){
        return tr[u][3];
    }

    inline T& siz(int u){
        return tr[u][4];
    }

    inline T& tag(int u){
        return tr[u][5];
    }

    inline T& root(){
        return rson(0);
    }
};

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 2);
        Splay<LL> st;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            st.update(a[i]);
            st.insert(a[i], i);
        }
        vector<LL> ans(n + 1);
        for(auto &[x, y] : st.toVector(1)){
            ans[y] = x;
        }
        for(int i = 1; i <= n; i++){
            cout << ans[i] << " ";
        }
        cout << endl;
    }
}

H 权值计算

计数、容斥

伪代码实际上计算的权值是：一个数组的每个前缀的不同数字个数之和，然后我们需要计算一个数组的每个子数组的权值之和。

我们先思考一个简单的问题，定义一个数组的权值为数组中所有数字的总和，然后计算一个数组的每个子数组的权值之和。

一个常见的转化就是，每个数出现在多少子数组中：对于 $a_i$ ，左端点在 $i$ 及以前（有 $i$ 个选择），右端点在 $i$ 及以后（有 $n - i + 1$ 个选择）的所有子数组都包含 $a_i$ ，答案就是 $\sum_{i=1}^n a_i \times i \times (n - i + 1))$ 。

再思考另一个问题，定义一个数组的权值为数组的不同数字个数，然后计算一个数组的每个子数组的权值之和。

类似上面的问题，将权值转化为每个数字再多少个子数组中有贡献。若数字 $x$ 出现在 $2$ 个位置 $l,r$ ，那么有多少个子数组至少包含一个 $x$ 呢？按照上面的结论：

对于第 $1$ 个 $x$ ，在 $l \times (n - l + 1)$ 个子数组中包含了第 $1$ 个 $x$ 。

对于第 $2$ 个 $x$ ，在 $r \times (n - r + 1)$ 个子数组中包含了第 $2$ 个 $x$ 。

那么有多少个子数组同时包含了两个 $x$ 呢？应该是 $l \times (n - r + 1)$ ，如果直接将第 $1、2$ 个 $x$ 的贡献求和，这些区间就会被多算。

所以 $x$ 的贡献应该是 $l \times (n - l + 1) + r \times (n - r + 1) - l \times (n - r + 1) = l \times (n - l + 1) + (r - l) \times (n - r + 1)$ 。

$l \times (n - l + 1)$ 实际上是第 $1$ 个 $x$ 的贡献，那么第 $2$ 个 $x$ 实际上的贡献就是 $(r - l) \times (n - r + 1)$ ，这个式子本质上其实是包含第 $2$ 个 $x$ 但不包含第 $1$ 个 $x$ 的子数组个数。

如果有第 $3$ 个 $x$ 在位置 $rr$ ，那包含第 $3$ 个 $x$ 但不包含第 $1、2$ 个 $x$ 的子数组个数就是 $(rr - r) \times (n - rr + 1)$ ，为什么跟 $l$ 没有关系呢？因为第 $1$ 个 $x$ 在第 $2$ 个 $x$ 左边，不包含第 $2$ 个 $x$ 一定不包含第 $1$ 个 $x$ 。

以此类推，对每一个 $x$ 求出贡献就可以解决这个问题了。

最后回到题目，注意到题目和第二个问题差了一个前缀，现在需要求一个 $x$ 在每个子数组的多少个前缀有贡献。

很显然如果 $x$ 在位置 $l$ ，一个包含 $l$ 的子数组所有右端点大于等于 $l$ 的前缀都会有 $x$ 产生的贡献。

子数组的贡献是 $l \times (n - l + 1)$ ，实际上这个东西有两部分， $l$ 是左端点不同的选法， $n - l + 1$ 是右端点的选法。

如果左端点固定，那么右端点的 $n - l + 1$ 种子数组对应的右端点大于等于 $l$ 的前缀个数分别是 $1，2，3，... n - l + 1$ ，总贡献就是 $(n - l + 1) \times (n - l + 1 + 1) / 2$ 。

再乘上左端点的选法，就是 $l \times (n - l + 1) \times (n - l + 1 + 1) / 2$ ，若不是第一个出现的 $x$ ，则为 $(r - l) \times (n - l + 1) \times (n - l + 1 + 1) / 2$

同第二个问题，对每个 $x$ 求出贡献即可。

时间复杂度： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        map<int, vector<int>> mp;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            mp[x].push_back(i);
        }
        auto ans = 0ll;
        for(auto &[x, y] : mp){
            y.insert(y.begin(), 0);
            for(int i = 1; i < y.size(); i++){
                int l = y[i - 1];
                int r = n - y[i] + 1;
                ans += 1ll * r * (r + 1) / 2 * (y[i] - l);
            }
        }
        cout << ans << endl;
    }
}

I 01回文

思维

我们需要发现一个性质：一个长度大于 $2$ 的 $01$ 串，首尾都是 $0/1$ ，且仅有 $2$ 个 $0/1$ 的话，那么它一定是回文串。

例如： $``1001$ 。

那如果矩阵有超过一个 $1$ ，那任意一个 $1$ 只要找到离他最近的 $1$ 的路径，就可以保证它们中间全都是 $0$ ，反之同理。

因此只要 $1$ 的个数大于 $1$ ，所有 $1$ 都是 $'Y'$ ， $0$ 的个数大于 $1$ ，所有 $0$ 都是 $'Y'$ 。

时间复杂度： $O(n \times m)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector s(n, string(m, '0'));
        array<int, 50> mp = {};
        for(auto &i : s){
            cin >> i;
            for(auto &j : i){
                mp[j]++;
            }
        }
        for(auto &i : s){
            for(auto &j : i){
                cout << "YN"[mp[j] == 1];
            }
            cout << endl;
        }
    }
}

J 终于再见

图论、BFS、最短路

首先需要发现一个结论：繁华度最多有大概 $\sqrt m$ 种。

因此直接按繁华度从大到小排序，用每种繁华度进行 BFS ，将初始值设置成 $0$ ，更新到达每个点的最短距离即可。

时间复杂度： $O(n \times \sqrt m)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector ve(n + 1, vector<int>());
    vector<int> deg(n + 1);
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    map<int, deque<int>> mp;
    for(int i = 1; i <= n; i++){
        mp[deg[i]].push_back(i);
    }
    vector<int> dis(n + 1, 1e9), ans(n + 1);
    for(auto &[x, q] : mp | views::reverse){
        for(auto &i : q){
            if(dis[i] > 1e8) dis[i] = -1;
            ans[i] = dis[i];
            dis[i] = 0;
        }
        while(q.size()){
            auto u = q.front();
            q.pop_front();
            for(auto &v : ve[u]){
                if(deg[v] >= x) continue;
                if(dis[v] > dis[u] + 1){
                    dis[v] = dis[u] + 1;
                    q.push_back(v);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}