day05b.cpp (1622B)
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <string> 5 #include <string_view> 6 #include <set> 7 #include <vector> 8 using namespace std; 9 10 vector<int> readints(string &s) { 11 vector<int> v; 12 stringstream sin(s); 13 int x; 14 15 while (sin >> x) 16 v.push_back(x); 17 18 return v; 19 } 20 21 bool valid(vector<int> &v, vector<pair<int, int>> &rules) { 22 for (unsigned i = 0; i < v.size(); i++) 23 for (unsigned j = i+1; j < v.size(); j++) 24 for (auto r : rules) 25 if (v[i] == r.second && v[j] == r.first) 26 return false; 27 return true; 28 } 29 30 bool canbenext(int x, vector<int> &v, bool picked[], vector<pair<int, int>> &rules) { 31 for (unsigned i = 0; i < v.size(); i++) { 32 if (picked[i]) 33 continue; 34 for (auto r : rules) 35 if (r.first == v[i] && r.second == x) 36 return false; 37 } 38 39 return true; 40 } 41 42 vector<int> sort(vector<int> &v, vector<pair<int, int>> &rules) { 43 vector<int> w; 44 bool picked[v.size()] = { 0 }; 45 46 while (w.size() < v.size()) { 47 for (unsigned i = 0; i < v.size(); i++) { 48 if (!picked[i] && canbenext(v[i], v, picked, rules)) { 49 picked[i] = true; 50 w.push_back(v[i]); 51 } 52 } 53 } 54 55 return w; 56 } 57 58 int main() { 59 string line; 60 vector<pair<int, int>> rules; 61 while (getline(cin, line)) { 62 if (line == "") 63 break; 64 65 replace(line.begin(), line.end(), '|', ' '); 66 auto v = readints(line); 67 int x = v[0]; 68 int y = v[1]; 69 rules.push_back(make_pair(x, y)); 70 } 71 72 int tot = 0; 73 while (getline(cin, line)) { 74 replace(line.begin(), line.end(), ',', ' '); 75 auto v = readints(line); 76 if (!valid(v, rules)) { 77 auto w = sort(v, rules); 78 tot += w[w.size()/2]; 79 } 80 } 81 cout << tot << endl; 82 return 0; 83 }