Codeforces Round #611 C. Friends and Gifts

Problem - C - Codeforces

概要

N項の数列が与えられる。この数列はもともと1からNまでの数字の順列であり、かつ任意のiに対しi番目の項はiではない。
現在この順列は一部が欠損しており、欠損部分が0となっている。この順列を復元せよ。ただし、いくつかの復元方法がある場合はどれを出力してもよい。

制約

2 ≦ N ≦ 2*10^5

方針

欠損部分について、項番側の配列(from)と順列側の配列(to)を準備する。from[i] = to[i]なるiが無いようにするべく、toの各項をスワップすることを考える。これはfrom[i] = to[i] となるiについて、swap(to[i], to[i+1])すればよい。ただし、m = to.size()と置いたときi = m - 1の場合については、swap(to[m-1], to[m-2])とすればよい。

解答

Submission #68178391 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	vector<int> from;
	vector<int> to;
 
	vector<bool> todecided(n, false);
	vector<int> a(n);
	rep(i, n){
		int x;
		cin >> x;
		x--;
		a[i] = x;
 
		if(x == -1) from.push_back(i);
		else todecided[x] = true;
	}
 
	rep(i, n){
		if(!todecided[i]) to.push_back(i);
	}
 
	int m = from.size();
	rep(i, m){
		if(from[i] == to[i]){
			if(i < m - 1){
				swap(to[i], to[i+1]);
			}else{
				swap(to[i-1], to[i]);
			}
		}
	}
 
	rep(i, m){
		a[from[i]] = to[i];
	}
 
	rep(i, n) cout << a[i] + 1 << (i == n - 1 ? "\n" : " ");
 
}