「Nhk R1 B」Basement-er Without Wings

NC230922. 「Nhk R1 B」Basement-er Without Wings

描述

给定一个序列 $x$ ，您需要构造一个长度为 $n$ 的排列 $a$ （从 $1$ 开始）满足 $\gcd(a_1,a_2,\cdots,a_i)=x_i$ 。输出一个满足上述条件的排列。

输入描述

第一行一个整数 ，表示排列长度。

第二行  个整数，其中第  个整数表示 ，含义如上所示。

输出描述

输出一行  个用空格分隔的整数，表示你构造的排列。

示例1

输入:

10
10 2 2 2 1 1 1 1 1 1

输出:

10 4 6 2 3 7 8 5 9 1

说明:

保证 $a$ 是一个 $n$ 的排列，且 $1 \leq x_i,a_i \leq n \leq 2 \times 10^6$ 。

数据保证有解。

请注意本题的时空限制。

原站题解

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

C++ 解法, 执行用时: 468ms, 内存消耗: 38468K, 提交时间: 2021-12-30 19:07:16

#include<bits/stdc++.h>
using namespace std;
#define N 2000010
int n,a[N],b[N],v[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		int x=a[i];
		if(a[i]==a[i-1])x=b[i-1];
		while(v[x])x+=a[i];
		b[i]=x;
		printf("%d%c",x,i<n?' ':'\n');
		v[x]=1;
	}
}

上一题

下一题

详情