Կետեր
Ռոբերտը, որպես ծննդյան նվեր ստացել է մի գլուխկոտրուկ։ Այն իրենից ներկայացնում է N հատ իրարից տարբեր, ամբողջ կոորդինատներով կետերի բազմություն, որոնք համարակալված են 1-ից N թվերով։ i-րդ կետի կոորդինատնենր են
(, ): Գլուխկոտրուկը լուծելու համար անհրաժեշտ է ընտրել այդ կետերի որևէ ենթաբազմություն, այնպես, որ բավարարվեն հետևյալ 3 պայմանները.- Ցանկացած t-ի համար գոյություն ունի առավելագույնը երկու ընտրված կետ, որոնց x-կորդինատը հավասար է t-ի։
- Ցանկացած t-ի համար գոյություն ունի առավելագույնը երկու ընտրված կետ, որոնց y-կորդինատը հավասար է t-ի:
- Ցանկացած չընտրված կետի համար, որի կոորդինատն է (x, y), կամ գոյություն ունեն երկու (a, y) և (b, y) կոորդինատներով ընտրված կետեր, որտեղ
a ≤ x ≤ b, կամ գոյություն ունեն երկու(x, a)և(x, b)կոորդինատներով ընտրված կետեր, որտեղa ≤ y ≤ b:
Ռոբերտը արագ գլխի ընկավ, որ գլուխկոտրուկը ունի լուծում կետերի ցանկացած բազմության համար և լուծեց այն։ Կարո՞ղ եք նույնը անել Դուք։
Մուտքային տվյալներ
Մուտքի առաջին տողը պարունակում է մեկ ամբողջ թիվ․ կետերի N քանակը
(1 ≤ N ≤ ): Հաջորդ N տողերից յուրաքանչյուրը պարունակում է և թվերը․ հերթական կետի կոորդինատները (1 ≤ , ≤ ):Ելքային տվյալներ
Ելքում պետք է արտածել 0-ներից և 1-երից բաղկացած N երկարության տող, որը հանդիսանում է գլուխկտորուկի լուծում, եթե նշվեն 1-երին համապատասխան գագաթները: Եթե լուծումը միակը չէ, կարող եք արտածել ցանկացածը:
Օրինակ
Մուտք | Ելք |
3
1 1
1 6
1 5 | 110 |
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) օրինակը
- Ենթախնդիր 1 (5 միավոր)
N ≤ 3
- Ենթախնդիր 2 (11 միավոր)
N ≤ 16
- Ենթախնդիր 3 (7 միավոր) Տրված կետերը հանդիսանում են (1, 1) կետը պարունակող ինչ-որ ուղղանկյան մեջ մտնող բոլոր ամբողջաթիվ կորդինատներով կետերի բազմություն:։
- Ենթախնդիր 4 (6 միավոր) Ցանկացած t-ի համար գոյություն ունեն առավելագույնը երկու կետեր, որոնց x-կորդինատը հավասար է t-ի:
- Ենթախնդիր 5 (31 միավոր)
N ≤ 5000
- Ենթախնդիր 6 (21 միավոր)
N ≤ 100000
- Ենթախնդիր 7 (19 միավոր) Լրացուցիչ սահմանափակումներ չկան։
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB