Решение задачи Красивые числа с Codeforces

Без пояснения   Просмотров: 64

Вам дана перестановка p=[p1,p2,…,pn] целых чисел от 1 до n. Назовем число m (1≤m≤n) красивым, если существует два индекса l,r (1≤l≤r≤n), таких что [pl,pl+1,…,pr] это перестановка чисел 1,2,…,m.

Например, пусть p=[4,5,1,3,2,6]. В этом случае числа 1,3,5,6 красивые, а 2,4 нет. Это так, потому что:

если l=3 и r=3 мы получим перестановку [1] для m=1;
если l=3 и r=5 мы получим перестановку [1,3,2] для m=3;
если l=1 и r=5 мы получим перестановку [4,5,1,3,2] для m=5;
если l=1 и r=6 мы получим перестановку [4,5,1,3,2,6] для m=6;
невозможно взять некоторые l и r, так что [pl,pl+1,…,pr] будет перестановкой чисел 1,2,…,m для m=2 и для m=4.
Вам дана перестановка p=[p1,p2,…,pn]. Для всех m (1≤m≤n) определите, является ли это число красивым или нет.

Код 

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int t,n;
int a[maxn],pos[maxn];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) 
		{
			cin>>a[i];
			pos[a[i]]=i; 
		}
		int mx=0,mi=1e9;
		for(int i=1;i<=n;i++)
		{
			mi=min(mi,pos[i]);
			mx=max(mx,pos[i]);
			if(mx-mi+1==i) cout<<"1";
			else cout<<"0";
		}
		cout<<endl;
	}
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта