#include<cstdio> #include<algorithm> #include<map> typedef std::map<int, int> mii; int n; int * r; int * w; int * t; int h = 0; int v = 0; int * vc; int * hc; int result = 0; mii vm; mii hm; void input() { scanf("%d", &n); r = new int[n]; w = new int[n]; t = new int[n]; for (int i = 0; i < n; ++i) { scanf("%d %d %d", r + i, w + i, t + i); if (r[i] == 1){ ++v; } else { ++h; } } } void remove_duplicates() { } void coefficients() { hc = new int[h]; vc = new int[v]; int vi = 0; int hi = 0; for (int i = 0; i < n; i++) { if (r[i] == 1) { vc[vi] = t[i] - w[i]; ++vi; } else { hc[hi] = t[i] - w[i]; ++hi; } } } void print_m(mii & m) { printf("\n"); for (mii::iterator i = m.begin(); i != m.end(); i++) { printf("%d %d\n", i -> first, i -> second); } } int max(int & a, int & b) { return a > b ? a : b; } int min(int & a, int & b) { return a < b ? a : b; } void solve() { for (int i = 0; i < h; i++) { if (hm.find(hc[i]) == hm.end()) { hm[hc[i]] = 1; } else { hm[hc[i]]++; } } for (int i = 0; i < v; i++) { if (vm.find(vc[i]) == vm.end()) { vm[vc[i]] = 1; } else { vm[vc[i]]++; } } // print_m(hm); // print_m(vm); for (mii::iterator it = hm.begin(); it != hm.end(); it++) { mii::iterator it2 = vm.find(it -> first); if (it2 != vm.end()) { result += min(it -> second, it2 -> second); } } } int main() { input(); remove_duplicates(); coefficients(); solve(); printf("%d\n", result); // printf("H\n"); // for (int i = 0; i < h; i++) { // printf("%d\n", hc[i]); // } // // printf("V\n"); // for (int i = 0; i < v; i++) { // printf("%d\n", vc[i]); // } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include<cstdio> #include<algorithm> #include<map> typedef std::map<int, int> mii; int n; int * r; int * w; int * t; int h = 0; int v = 0; int * vc; int * hc; int result = 0; mii vm; mii hm; void input() { scanf("%d", &n); r = new int[n]; w = new int[n]; t = new int[n]; for (int i = 0; i < n; ++i) { scanf("%d %d %d", r + i, w + i, t + i); if (r[i] == 1){ ++v; } else { ++h; } } } void remove_duplicates() { } void coefficients() { hc = new int[h]; vc = new int[v]; int vi = 0; int hi = 0; for (int i = 0; i < n; i++) { if (r[i] == 1) { vc[vi] = t[i] - w[i]; ++vi; } else { hc[hi] = t[i] - w[i]; ++hi; } } } void print_m(mii & m) { printf("\n"); for (mii::iterator i = m.begin(); i != m.end(); i++) { printf("%d %d\n", i -> first, i -> second); } } int max(int & a, int & b) { return a > b ? a : b; } int min(int & a, int & b) { return a < b ? a : b; } void solve() { for (int i = 0; i < h; i++) { if (hm.find(hc[i]) == hm.end()) { hm[hc[i]] = 1; } else { hm[hc[i]]++; } } for (int i = 0; i < v; i++) { if (vm.find(vc[i]) == vm.end()) { vm[vc[i]] = 1; } else { vm[vc[i]]++; } } // print_m(hm); // print_m(vm); for (mii::iterator it = hm.begin(); it != hm.end(); it++) { mii::iterator it2 = vm.find(it -> first); if (it2 != vm.end()) { result += min(it -> second, it2 -> second); } } } int main() { input(); remove_duplicates(); coefficients(); solve(); printf("%d\n", result); // printf("H\n"); // for (int i = 0; i < h; i++) { // printf("%d\n", hc[i]); // } // // printf("V\n"); // for (int i = 0; i < v; i++) { // printf("%d\n", vc[i]); // } return 0; } |