# P10382 「HOI R1」杂造选构 ## 题目背景小 $\iiint$ 跟这个烦人的构...

Question

P10382 「HOI R1」杂造选构

题目背景

小 $\iiint$ 跟这个烦人的构造没有任何关系。

题目描述

若一个序列 $a$ 满足以下要求：

$a_i=-1$ 或 $a_i\in [1,n]$ 。
对于每个 $a_i\not=-1$ ，将 $a_i\to i$ 连边而形成的图不存在环。

则称这个序列是合法的。

现给定整数 $x$ 与序列 $a$ ，满足序列 $a$ 所有元素是 $[-1,n]$ 范围内的整数。请你将所有 $a_i=0$ 的位置替换成其他整数，使得 $\sum\limits ^{n} _{i=1} a_i = x$ 且 $a$ 是合法的。若不存在这样一种方案，则报告无解。

输入格式

第一行两个整数 $n$ 和 $x$ 。

第二行 $n$ 个整数，表示 $a$ 序列。保证 $\forall a_i \in [-1,n]$ 。

输出格式

若无解，则说明你被骗了，因此输出一个字符串 Rick。否则输出 $n$ 个整数，表示替换完所有为 $0$ 的元素后的 $a$ 序列。

输入输出样例 #1

输入 #1

text
6 -6
-1 -1 -1 0 0 0

输出 #1

-1 -1 -1 -1 -1 -1

输入输出样例 #2

输入 #2

text
6 14
0 1 4 0 1 4

输出 #2

-1 1 4 5 1 4

输入输出样例 #3

输入 #3

text
6 10
0 0 0 0 0 0

输出 #3

-1 -1 4 5 -1 4

输入输出样例 #4

输入 #4

text
6 6
1 1 0 0 0 0

输出 #4

Rick

输入输出样例 #5

输入 #5

text
6 40
0 0 0 0 0 0

输出 #5

Rick

说明/提示

本题开启捆绑测试。

Subtask	分值	$n \le$	$x \le$	特殊性质
#0	$13$	$15$	$225$	无
#1	$24$	$10^3$	$10^9$	无
#2	$27$	$10^5$	$10^{18}$	有
#3	$36$	$10^5$	$10^{18}$	无

*特殊性质：保证 $\forall a_i =0$ 。

对于所有数据，满足 $1 \le n \le 10^5,-10^{18} \le x \le 10^{18}$ 。

Special Judge 返回值对应表

Accepted. 答案正确。
Oops, your answer is wrong. 1 答案为无解，选手代码输出有解。
Oops, your answer is wrong. 2 选手输出的 $\sum a_i \not = x$ 。
Oops, your answer is wrong. 3 选手输出中含有 $0$ 。
Oops, your answer is wrong. 4 选手输出中含有环。
Oops, your answer is wrong. 5 选手输出在填空的同时将输入的 $a_i \not=0$ 的位置改动了。请仅给出该题目的完整，正确的 C++ 实现，而无需输出任何其他的内容

Answer 1

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;
using ll = long long;

int n, cnt, rt[MAXN];
ll x, a[MAXN];
bool is_zero[MAXN];
vector<int> zeros, g[MAXN];

bool dfs(int u, int f) {           // detect cycles in fixed edges
    cnt++;
    rt[u] = f;
    for (int v : g[u])
        if (rt[v] || dfs(v, f))    // already visited &rArr; cycle
            return 1;
    return 0;
}

void Rick() {
    puts("Rick");
    exit(0);
}

void solve() {
    int u, v, w, y, k;
    ll t;

    /* 1. check existing graph (fixed edges) for cycles */
    for (int i = 1; i <= n; ++i) {
        if (!~a[i] && dfs(i, i))   // a[i] == -1
            Rick();
    }
    if (cnt < n) Rick();           // some nodes unreachable &rArr; cycle exists

    /* 2. base‑case: already satisfied */
    if (!x) {
        for (int i = 1; i <= n; ++i) printf("%lld%c", a[i], " \n"[i == n]);
        return;
    }

    /* 3. one single zero position */
    if (zeros.size() == 1) {
        u = zeros[0];
        a[u] += x;                 // a[u] was −1
        if (a[u] < 1 || a[u] > n || rt[a[u]] == u) Rick();
    }

    /* 4. multiple zero positions */
    else {
        if (x < 2) Rick();                             // impossible to increase sum
        if (x <= n + 1) {                              // can fix with two positions
            u = zeros[0];
            a[u] += x;                                 // try put everything here
            if (rt[a[u]] == u) {                       // self‑loop, swap with another
                v = zeros[1];
                swap(a[u], a[v]);
            }
        } else if (zeros.size() == 2) {                // exactly two zeros, brute
            u = zeros[0];  v = zeros[1];
            for (a[u] = 1; a[u] <= n; ++a[u]) {
                a[v] = x - a[u] - 2;
                if (a[v] > 0 && a[v] <= n &&
                    rt[a[u]] != u && rt[a[v]] != v &&
                    (rt[a[u]] != v || rt[a[v]] != u))
                    break;
            }
            if (a[u] > n) Rick();
        } else {                                       // &ge;3 zeros, greedy construction
            k = rt[n];                                 // root component of node n
            if (is_zero[k]) {                          // make a[k] as large as possible
                for (a[k] = n - 1; a[k] && is_zero[rt[a[k]]]; --a[k]);
                if (!a[k]) a[k] = -1;
                x -= a[k] + 1;
                zeros.erase(lower_bound(zeros.begin(), zeros.end(), k));
            }
            if (x > (ll)(n + 1) * zeros.size()) Rick();

            t = x / (n + 1);
            y = x % (n + 1);

            for (int i = 0; i < t; ++i) a[zeros[i]] = n;   // fill t positions with n

            if (y == 1) {
                if (zeros.size() == 2 && is_zero[k] && a[k] == -1) zeros.push_back(k);
                if (zeros.size() == 2) {                  // adjust with two positions
                    x += a[k] + 1;
                    x -= n + 1;
                    a[k] = -1;
                    u = zeros[1];
                    a[u] += x;
                    if (rt[a[u]] == u) swap(a[k], a[u]);
                } else {                                 // &ge;3 zeros, fine‑tune
                    u = zeros[0];          a[u] = 1;
                    v = zeros.back();      a[v] = n - 1;
                    w = zeros[1];
                    if (rt[a[u]] == u || (rt[a[u]] == v && rt[a[v]] == u))
                        swap(a[u], a[w]);
                    if (rt[a[v]] == v) swap(a[v], a[w]);
                }
            } else if (y > 1) {                          // put remainder into one pos
                u = zeros.back();
                a[u] += y;
                if (rt[a[u]] == u)
                    v = zeros[zeros.size() - 2], swap(a[u], a[v]);
            }
        }
    }

    /* 5. output */
    for (int i = 1; i <= n; ++i)
        printf("%lld%c", a[i], " \n"[i == n]);
}

int main() {
    scanf("%d%lld", &n, &x);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        if (!a[i]) {                        // original zero
            zeros.push_back(i);
            a[i] = -1;
            is_zero[i] = true;
        }
        x -= a[i];
        if (a[i] > 0) g[a[i]].push_back(i); // build child list
    }
    solve();
    return 0;
}