D. Rating compression (thinking + double pointer)

Codeforces Global Round 12

Problem

Give a length of n Array of a, among $1\le a[i]\le n$.
$b[j]=mi{n}_{j\le i\le j+k-1}a[i]$
Judge k = 1 ~ n when , Got b Whether the array is an arrangement .

Solution

1. 1 Is the smallest number , And can only be located in a The beginning or end of an array , And only once .
   otherwise ,$an{s}_{k=n}=1,an{s}_{1\le k\le n-1}=0$.
2. When a When the array itself is an arrangement ,$an{s}_1=1$
3. Maintain a range $[l,r]$, loop j = 1, 2, 3,···.
   When $a_{l}orperson{a}_r$ be equal to i When , And $min(a[l,r])=i+1$,
   be $an{s}_{n-i}=1$, Otherwise, the program will be terminated .
   Finally, when $2\le k<n-i$ when ,ans = 0; When $n-i\le k\le n$ when , ans = 1.

This topic is not so much thinking , It's more a conclusion question . In fact, one of the characteristics of the arrangement itself . This kind of algorithm needs more problem summaries .

Code

Time complexity $O(n)$

const int N = 3e5 + 5, M = 1e6 + 7;

int a[N], ans[N], cnt[N];

int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
			cnt[i] = ans[i] = 0;

		for (int i = 1; i <= n; i++)
		{
    
			cin >> a[i];
			cnt[a[i]]++;
		}

		//k = 1
		int  f = 1;
		for (int i = 1; i <= n; i++)
			if (cnt[i] == 0) f = 0;
		if (f) ans[1] = 1;
		//k = n
		if (cnt[1]) ans[n] = 1;

		//1 < k < n
		int l = 1, r = n;
		int j = 1;
		while (l < r)
		{
    
			//--cnt[j] Ensure that only one of the left and right endpoints is equal to j
			if (--cnt[j] == 0 && (a[l] == j || a[r] == j) && cnt[j + 1])
			{
    
				ans[n - j] = 1;
				l += a[l] == j;
				r -= a[r] == j;
				j++;
			}
			else break;
		}


		for (int i = 1; i <= n; i++)
			cout << ans[i];
		cout << "\n";
	}


	return 0;
}