시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB187163551734.103%

문제

남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.

모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형이 있다. (자신보다 키가 큰 남자, 작은 남자) 키가 같은 남자와 여자가 춤을 추는 일은 일어나지 않는다.

이때, 상근이는 각 사람의 키와 선호하는 이성 유형을 알고 있다. 이런 조건을 가지고 춤을 출 쌍을 만들어 주려고 한다. 상근이는 최대 몇 쌍을 만들 수 있을까?

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 남자의 키가 밀리미터 단위로 주어진다. 키는 절댓값이 1500보다 크거나 같고, 2500보다 작거나 같은 정수이다. 사람의 키는 주어지는 값의 절댓값이다. 키가 양수인 경우에는 자신보다 키가 큰 여자와 춤을 추기를 원하는 남자이고, 음수인 경우에는 키가 작은 사람과 춤을 추기를 원하는 남자이다.

셋째 줄에는 여자의 키가 밀리미터 단위로 주어진다. 키의 범위나 의미 역시 남자와 동일하다. 

출력

첫째 줄에 상근이가 만들어 줄 수 있는 쌍의 최댓값을 출력한다.

예제 입력 1

1
-1800
1800

예제 출력 1

0

예제 입력 2

1
1700
-1800

예제 출력 2

1

예제 입력 3

2
-1800 -2200
1900 1700

예제 출력 3

2
W3sicHJvYmxlbV9pZCI6IjI4MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDRcdWMyYTQgXHVkMzBjXHVkMmYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIwYThcdWM3OTAgTlx1YmE4NVx1YWNmYyBcdWM1ZWNcdWM3OTAgTlx1YmE4NVx1Yzc3NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOGZjXHVjZDVjXHVkNTVjIFx1YjMwNFx1YzJhNCBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVjNjU0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWQwYTRcdWI5N2MgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViMGE4XHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM1ZWNcdWM3OTBcdWIyOTQgXHViMGE4XHVjNzkwXHVjNjQwIFx1Y2RhNFx1Yzc0NCBcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWNkYTRcdWM3NDQgXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIwYThcdWM3OTBcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWIwYThcdWM3OTBcdWFjMDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YzVlY1x1Yzc5MFx1YjI5NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YzcyMFx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1ZDU1YyBcdWM3MjBcdWQ2MTVcdWM3NDAgXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHVjNWVjXHVjNzkwXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjNzIwXHVkNjE1XHVjNzQwIFx1Yzc5MFx1YzJlMFx1YmNmNFx1YjJlNCBcdWQwYTRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzcyMFx1ZDYxNVx1Yzc3NFx1YjJlNC4gXHVjNWVjXHVjNzkwXHViM2M0IFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWIwYThcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWM1ZWNcdWM3OTBcdWFjMDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YjBhOFx1Yzc5MFx1YjNjNCBcdWIwYThcdWM3OTBcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjIFx1YjQ1MCBcdWM3MjBcdWQ2MTVcdWM3NzQgXHVjNzg4XHViMmU0LiAoXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHViMGE4XHVjNzkwLCBcdWM3OTFcdWM3NDAgXHViMGE4XHVjNzkwKSBcdWQwYTRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWM1ZWNcdWM3OTBcdWFjMDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjI5NCBcdWM3N2NcdWM3NDAmbmJzcDtcdWM3N2NcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzU4IFx1ZDBhNFx1YzY0MCBcdWMxMjBcdWQ2MzhcdWQ1NThcdWIyOTQgXHVjNzc0XHVjMTMxIFx1YzcyMFx1ZDYxNVx1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWNkYTRcdWM3NDQgXHVjZDljIFx1YzMwZFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHVjMzBkXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwYThcdWM3OTBcdWM3NTggXHVkMGE0XHVhYzAwIFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMCBcdWIyZThcdWM3MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQwYTRcdWIyOTQgXHVjODA4XHViMzEzXHVhYzEyXHVjNzc0IDE1MDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjUwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMGFjXHViNzhjXHVjNzU4IFx1ZDBhNFx1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMxM1x1YWMxMlx1Yzc3NFx1YjJlNC4gXHVkMGE0XHVhYzAwIFx1YzU5MVx1YzIxOFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHVjNWVjXHVjNzkwXHVjNjQwIFx1Y2RhNFx1Yzc0NCBcdWNkOTRcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjBhOFx1Yzc5MFx1Yzc3NFx1YWNlMCwgXHVjNzRjXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWQwYTRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWNkYTRcdWM3NDQgXHVjZDk0XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIwYThcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWVjXHVjNzkwXHVjNzU4IFx1ZDBhNFx1YWMwMCBcdWJjMDBcdWI5YWNcdWJiZjhcdWQxMzAgXHViMmU4XHVjNzA0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMGE0XHVjNzU4IFx1YmM5NFx1YzcwNFx1YjA5OCBcdWM3NThcdWJiZjggXHVjNWVkXHVjMmRjIFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWIzZDlcdWM3N2NcdWQ1NThcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0XHVjNWI0IFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzMwZFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTEVTIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBib3lzIGFuZCBOIGdpcmxzIGF0IGEgZGFuY2UgcGFydHkuIFdlIGhhdmUgbWVhc3VyZWQgdGhlaXIgaGVpZ2h0cy4gRWFjaCBib3kgd2lsbCBvbmx5IGRhbmNlIHdpdGggYSBnaXJsIGFuZCBlYWNoIGdpcmwgd2lsbCBvbmx5IGRhbmNlIHdpdGggYSBib3kuIEV2ZXJ5b25lIHdpbGwgZGFuY2Ugd2l0aCBhdCBtb3N0IG9uZSBwYXJ0bmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGJveSBlaXRoZXIgd2FudHMgdG8gZGFuY2Ugd2l0aCBhIGdpcmwgd2hvIGlzIHRhbGxlciB0aGFuIGhpbSBvciB3aXRoIGEgZ2lybCB3aG8gaXMgc2hvcnRlciB0aGFuIGhpbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW5hbG9nb3VzbHksIGVhY2ggZ2lybCBlaXRoZXIgd2FudHMgdG8gZGFuY2Ugd2l0aCBhIGJveSB3aG8gaXMgdGFsbGVyIHRoYW4gaGVyIG9yIHdpdGggYSBib3kgd2hvIGlzIHNob3J0ZXIgdGhhbiBoZXIuIEJveXMgYW5kIGdpcmxzIHdobyBhcmUgZXF1YWxseSB0YWxsIG5ldmVyIHdhbnQgdG8gZGFuY2Ugd2l0aCBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZXNwZWN0aW5nIGV2ZXJ5b25lJiMzOTtzIHdpc2hlcywgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiBkYW5jaW5nIHBhaXJzIHRoYXQgY2FuIGJlIGFjaGlldmVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgd2hvc2UgYWJzb2x1dGUgdmFsdWVzIGFyZSBiZXR3ZWVuIDE1MDAgYW5kIDI1MDAsIGluY2x1c2l2ZS4gVGhlaXIgYWJzb2x1dGUgdmFsdWVzIHJlcHJlc2VudCB0aGUgaGVpZ2h0IG9mIGVhY2ggb2YgdGhlIGJveXMgaW4gbWlsbGltZXRyZXMuIFBvc2l0aXZlIGhlaWdodCB2YWx1ZXMgaW5kaWNhdGUgYm95cyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGdpcmxzIHRhbGxlciB0aGFuIHRoZW1zZWx2ZXMsIHdoaWxlIG5lZ2F0aXZlIGhlaWdodCB2YWx1ZXMgaW5kaWNhdGUgYm95cyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGdpcmxzIHNob3J0ZXIgdGhhbiB0aGVtc2VsdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGludGVnZXJzIHdob3NlIGFic29sdXRlIHZhbHVlcyBhcmUgYmV0d2VlbiAxNTAwIGFuZCAyNTAwLCBpbmNsdXNpdmUuIFRoZWlyIGFic29sdXRlIHZhbHVlcyByZXByZXNlbnQgdGhlIGhlaWdodCBvZiBlYWNoIG9mIHRoZSBnaXJscyBpbiBtaWxsaW1ldHJlcy4gUG9zaXRpdmUgaGVpZ2h0IHZhbHVlcyBpbmRpY2F0ZSBnaXJscyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGJveXMgdGFsbGVyIHRoYW4gdGhlbXNlbHZlcywgd2hpbGUgbmVnYXRpdmUgaGVpZ2h0IHZhbHVlcyBpbmRpY2F0ZSBnaXJscyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGJveXMgc2hvcnRlciB0aGFuIHRoZW1zZWx2ZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtYXhpbXVtIG51bWJlciBvZiBkYW5jaW5nIHBhaXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #1 4번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013