Codeforces Round #623 (Div. 2, based on VK Cup 2019-2020 - Elimination Round, Engine) C. Restoring

风骨散人Chiam

发布于 2020-10-29 09:45:06

5110

发布于 2020-10-29 09:45:06

文章被收录于专栏：CSDN旧文

C. Restoring Permutation time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output You are given a sequence b1,b2,…,bn. Find the lexicographically minimal permutation a1,a2,…,a2n such that bi=min(a2i−1,a2i), or determine that it is impossible.

Input Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤100).

The first line of each test case consists of one integer n — the number of elements in the sequence b (1≤n≤100).

The second line of each test case consists of n different integers b1,…,bn — elements of the sequence b (1≤bi≤2n).

It is guaranteed that the sum of n by all test cases doesn’t exceed 100.

Output For each test case, if there is no appropriate permutation, print one number −1.

Otherwise, print 2n integers a1,…,a2n — required lexicographically minimal permutation of numbers from 1 to 2n.

Example inputCopy 5 1 1 2 4 1 3 4 1 3 4 2 3 4 5 5 1 5 7 2 8 outputCopy 1 2 -1 4 5 1 2 3 6 -1 1 3 5 6 7 9 2 4 8 10 暴力暴力，

#include <bits/stdc++.h>
using namespace std;
 
int a[1000], b[1000], n, t;
bool vis[1000];
void solve()
{
    bool r=1;
    for (int i = 1; i <= n; ++i)
    {
        b[2 * i - 1] = a[i];
        r = 1;
        for (int j = a[i]; j <= 2 * n; ++j)
            if (!vis[j])
            {
                b[2 * i] = j;
                vis[j] = 1;
                r = 0;
                break;
            }
        if (r == 1)
            break;
    }
    r = 1;
    for (int i = 1; i <= 2 * n; ++i)
        if (b[i] == 0)
        {
            r = 0;
            break;
        }
    if (r == 0)
        puts("-1");
    else
    {
        for (int i = 1; i <= 2 * n; ++i)
            cout << b[i] << ' ';
        cout << endl;
    }
}
int main()
{
    cin >> t;
    while (t--)
    {
        memset(vis, 0, sizeof vis);
        memset(b, 0, sizeof b);
        cin >> n;
        bool r = 1;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            vis[a[i]] = 1;
            if (a[i] == 2 * n)
                r = 0;
        }
        if (r == 0)
 
            puts("-1");
        else
            solve();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/02/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除