Số thú vị

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 250M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Hôm nay [user:thuongchirox9] được học về hoán vị. Vì bài tập trên trường quá dễ, [user:thuongchirox9] ngu ngốc đã thách thức nganngan2710: hãy ra 1 bài toán về hoán vị thú dị mà [user:thuongchirox9] không giải được, còn không nganngan2710 chỉ là một con gà. Thật không ngờ nganngan2710 không phải là một con gà, [user:thuongchirox9] đã không giải được vì nó quá khó TT. Bạn hãy giúp [user:thuongchirox9], nếu không bạn cũng là một con gà :))))

Bài toán như sau: thuong_chirox9 được cho một dãy hoán vị p=[p1,p2,,pn] của các số nguyên từ 1 đến n. Hãy gọi số m (1mn) là số thú dị, nếu tồn tại hai chỉ số l,r(1lrn), sao cho các số [pl,pl+1 ,,pr] là một hoán vị của các số nguyên 1,2,,m.

Ví dụ, cho p=[4,5,1,3,2,6]. Trong trường hợp này, các số 1,3,5,6 là thú vị và 2,4 thì không. Đó là vì:

  • Nếu l=3r=3 chúng ta sẽ có một hoán vị [1] cho m=1;

  • Nếu l=3r=5 ta sẽ có một hoán vị [1,3,2] cho m=3;

  • Nếu l=1r=5 ta sẽ có một hoán vị [4,5,1,3,2] cho m=5;

  • Nếu l=1r=6 ta sẽ có một hoán vị [4,5,1,3,2,6] cho m=6;

  • Không thể lấy lr nào đó sao cho [pl,pl+1 ,,pr] là hoán vị của các số 1,2,,m với m=2m=4.

Input:

Dòng đầu tiên chứa số n(1n2.105) - độ dài của hoán vị p đã cho.

Dòng tiếp theo chứa n số nguyên p1,p2,,pn(1pin), tất cả các số pi đều khác nhau).

Output: là chuỗi có độ dài n, trong đó ký tự thứ i bằng 1 nếu i là một số thú vị và bằng 0 nếu i không phải là một số thú vị.

Ví dụ:

Input
Copy
6
4 5 1 3 2 6
Output
Copy
101011

Comments

Please read the guidelines before commenting.


There are no comments at the moment.