/home/toolbox/public_html/solutions/107/10763/judged.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 /*
11 * Author: Matthew Eastman
12 * Date: 2006-06-22
13 * Purpose: Contest Practice
14 * Problem: 10763 - Foreign Exchange <http://isaac.lsu.edu/udv/v107/10763.html>
15 */
16
17 #define TRUE (1 == 1)
18 #define FALSE (1 != 1)
19
20 #define DEBUG if (FALSE)
21
22 #define MAX_CANDIDATES 500000
23
24 struct candidate_s
25 {
26 int a;
27 int b;
28 };
29 int num_candidates;
30 int list_size_ab;
31 int list_size_ba;
32 struct candidate_s candidates_ab[MAX_CANDIDATES / 2 + 5];
33 struct candidate_s candidates_ba[MAX_CANDIDATES / 2 + 5];
34
35 void init()
36 {
37 /* FUNCTION init */
38 } /* FUNCTION init */
39
40 void dump()
41 {
42 /* FUNCTION dump */
43 } /* FUNCTION dump */
44
45 int getInput()
46 {
47 /* FUNCTION getInput */
48 int dataReadFlag;
49
50 num_candidates = 0;
51 scanf("%d", &num_candidates);
52 if (0 == num_candidates)
53 dataReadFlag = FALSE;
54 else
55 dataReadFlag = TRUE;
56
57 return (dataReadFlag);
58 } /* FUNCTION getInput */
59
60 void bail(int remaining)
61 {
62 int i;
63
64 for (i = 0; i < remaining; i++)
65 {
66 scanf("%*d %*d");
67 }
68
69 printf("NO\n");
70 }
71
72 int compare_a(const void *a, const void *b)
73 {
74 struct candidate_s *c_a = a;
75 struct candidate_s *c_b = b;
76
77 return c_b->a - c_a->a;
78 }
79
80 void process()
81 {
82 /* FUNCTION process */
83 int a, b, i;
84 size_t cmp_size;
85
86 if (num_candidates % 2)
87 {
88 bail(num_candidates);
89 return;
90 }
91
92 list_size_ab = 0;
93 list_size_ba = 0;
94
95 for (i = 0; i < num_candidates; i++)
96 {
97 scanf("%d %d", &a, &b);
98 if (a < b)
99 {
100 candidates_ab[list_size_ab].a = a;
101 candidates_ab[list_size_ab].b = b;
102 list_size_ab++;
103
104 if (list_size_ab > num_candidates / 2)
105 {
106 bail(num_candidates - i - 1);
107 return;
108 }
109 }
110 else
111 {
112 candidates_ba[list_size_ba].a = b;
113 candidates_ba[list_size_ba].b = a;
114 list_size_ba++;
115
116 if (list_size_ba > num_candidates / 2)
117 {
118 bail(num_candidates - i - 1);
119 return;
120 }
121 }
122 }
123
124 if (list_size_ab != list_size_ba)
125 {
126 bail(0);
127 return;
128 }
129
130 qsort(candidates_ab, list_size_ab, sizeof(struct candidate_s), compare_a);
131 qsort(candidates_ba, list_size_ba, sizeof(struct candidate_s), compare_a);
132
133 cmp_size = sizeof(struct candidate_s) * list_size_ab;
134 if (0 == memcmp(candidates_ab, candidates_ba, cmp_size))
135 printf("YES\n");
136 else
137 printf("NO\n");
138 } /* FUNCTION process */
139
140 int main ()
141 {
142 /* main */
143 int moreToDo;
144
145 init();
146 moreToDo = getInput();
147 while (moreToDo)
148 {
149 /* while */
150 process();
151 moreToDo = getInput();
152 } /* while */
153
154 return EXIT_SUCCESS;
155 } /* main */
156
157