列表

详情


NC248904. 构造

描述

给定n,a,b,请构造一个长度为2n的排列P,满足如下条件:
\forall 1\le i < 2n , pre_{i} \neq suf_{i},且P_{a} = b。其中pre_{i}代表排列的前i个数之和,suf_{i}则代表排列的后i个数之和。

如果存在多种答案,任意输出一种即可。可以证明,答案一定存在。

输入描述

第一行数据组数t(1\le t \le 10^4)
对于每组数据,一行三个整数n,a,b(1\le a,b \le 2n, 1\le n \le 2\cdot 10^5)
保证所有的n之和不超过2\cdot 10^5

输出描述

对于每组数据,输出一行2n个整数,表示该排列。

示例1

输入:

3
2 3 4
4 6 1
5 1 3

输出:

3 1 4 2
2 3 7 5 6 1 4 8
3 1 6 10 2 4 7 8 9 5

说明:

对于第一个样例
pre_{1} = 3 \ne 2 = suf_{1}
pre_{2} = 4 \ne 6 = suf_{2}
pre_{3} = 8 \ne 7 = suf_{3}
故满足条件

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 80ms, 内存消耗: 4584K, 提交时间: 2023-03-17 22:15:57

#include<bits/stdc++.h>
using namespace std;
const int max_n=2e5+5;
int P[max_n<<1];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,a,b;
		scanf("%d%d%d",&n,&a,&b);
		if((a<=n)==(b<=n))
		{
			for(int i=1;i<=2*n;++i)
				P[i]=i;
			if(P[a]!=b)
				swap(P[a],P[b]);
		}
		else
		{
			for(int i=1;i<=2*n;++i)
				P[i]=2*n+1-i;
			if(P[a]!=b)
				swap(P[a],P[2*n+1-b]);
		}
		//assert(P[a]==b);
		for(int i=1;i<=2*n;++i)
			printf("%d%c",P[i]," \n"[i==2*n]);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 73ms, 内存消耗: 4688K, 提交时间: 2023-04-12 16:15:24

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000005;
int p[M];
int main()
{
	int n,a,b,t;
	cin>>t;
	while(t--)
	{
		cin>>n>>a>>b;
		p[a]=b;
		if(a<=n&&b<=n||a>n&&b>n)
		{
			for(int i=1;i<=n*2;i++) p[i]=i;
			swap(p[a],p[b]);
		}
		else
		{
			for(int i=n*2;i>=1;i--) p[n*2+1-i]=i;
			swap(p[a],p[n*2+1-b]);
		}
		for(int i=1;i<=n*2;i++) printf("%d ",p[i]);
		cout<<endl;
	}
	return 0;
}

pypy3 解法, 执行用时: 476ms, 内存消耗: 48820K, 提交时间: 2023-03-17 19:25:14

import sys

input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
li = lambda: list(mii())

t = ii()
for _ in range(t):
    n, a, b = mii()
    if (a > n) ^ (b > n):
        res = [0] + list(range(n * 2, 0, -1))
        b = n * 2 - b + 1
    else:
        res = [0] + list(range(1, n * 2 + 1))
    res[a], res[b] = res[b], res[a]
    print(*res[1:])

上一题