CF101532B Array Reconstructing(暴力模拟)

题面：

You are given an array a consisting of n elements a1, a2, ..., an. Array a has a special property, which is:

                                                ai = ( ai - 1 + 1) % m, for each i (1 < i ≤ n)

You are given the array a with some lost elements from it, each lost element is replaced by -1. Your task is to find all the lost elements again, can you?

 

Input：

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 1000) (1 ≤ m ≤ 109), where n is the size of the array, and m is the described modulus in the problem statement.

The second line of each test case contains n integers a1, a2, ..., an ( - 1 ≤ ai < m), giving the array a. If the ith element is lost, then ai will be -1. Otherwise, ai will be a non-negative integer less than m.

It is guaranteed that the input is correct, and there is at least one non-lost element in the given array.

 

Output:

For each test case, print a single line containing n integers a1, a2, ..., an, giving the array a after finding all the lost elements.

It is guaranteed that an answer exists for the given input.

 

Example:

 

Note：

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

 

分析：

暑假集训第一天，咸鱼的复健之旅，大夏天的重庆真是好热啊……定级赛中签到题的存在，竟然WA了三发真是太丢人了。我从最开始也想到了会不会第一个数就是-1，但是例子没有给出来我就没多想，根据WA的情况分析果然是存在这种情况的吧，所以不能从最开始一步步往后推，要先找到第一个不为-1的数，以它为起点向两侧推过去，如果后一个数为0，那么前一个数就为m-1是一个要考虑到的小情况，然后没什么坑了，暴力模拟。

 

AC代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 1010;
int t, n, m, u;
long long num[maxn];

int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		u = -1;
		for(int i = 0; i < n; i++) {
			scanf("%lld", &num[i]);
			if(u == -1){
				if(num[i] != -1) u = i;
			}
		}
		for(int i = u - 1; i >= 0; i--){
			if(num[i+1] == 0) num[i] = m - 1;
			else num[i] = num[i+1] - 1;
		}
		for(int i = u + 1; i < n; i++){
			num[i] = (num[i-1]+1) % m;
		}
		for(int i = 0; i < n; i++){
			if(i) cout<<" ";
			printf("%lld",num[i]);
		}
		cout<<endl;
	}
	return 0;
}