submission-wa.cpp (2714B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 // NOTE: This got a contest WA on held out set. I think this is just excessively complex. 13 14 //- p, q strings 15 //- p as product of variables written in the numerator of a fraction 16 //- q as product of variables written in the denominator of a fraction 17 //- can we mutate this such that the numerator simplified to "six" and denominator is cleared? 18 // - return YES / NO 19 20 int main() { 21 22 int testCases, current, pSize, qSize; 23 string p, q = ""; 24 25 cin >> testCases; 26 27 // idea: 28 // put into hashmap, count numbers, ensure sDelta = 1, iDelta = 1, xDelta = 1, all rest = 0 29 30 for(int z = 0; z < testCases; ++z) { 31 cin >> pSize; 32 cin >> qSize; 33 cin >> p; 34 cin >> q; 35 36 unordered_map<char,int> pCounts {}; 37 38 for(int i = 0; i < pSize; ++i) { 39 pCounts[p[i]] += 1; 40 } 41 42 unordered_map<char,int> qCounts {}; 43 bool ctn = false; 44 45 for(int i = 0; i < qSize; ++i) { 46 if(!pCounts.contains(q[i])) { 47 cout << "NO" << endl; 48 ctn = true; 49 break; 50 } 51 qCounts[q[i]] += 1; 52 } 53 54 if(ctn) { 55 continue; 56 } 57 58 59 bool fs = false; 60 bool fi = false; 61 bool fx = false; 62 bool bad = false; 63 64 for(auto& ele : pCounts) { 65 66 if(ele.second > qCounts[ele.first]) { 67 int delta = ele.second - qCounts[ele.first]; 68 69 if(delta >= 2) { 70 bad = true; 71 break; 72 } 73 74 if(ele.first == 's') { 75 if(fs) { 76 bad = true; 77 break; 78 } 79 fs = true; 80 } 81 else if(ele.first == 'i') { 82 if(fi) { 83 bad = true; 84 break; 85 } 86 fi = true; 87 } 88 else if(ele.first == 'x') { 89 if(fx) { 90 bad = true; 91 break; 92 } 93 fx = true; 94 } 95 else { 96 bad = true; 97 break; 98 } 99 } 100 } 101 if(fs && fi && fx) { 102 if(!bad) { 103 cout << "YES" << endl; 104 } else { 105 cout << "NO" << endl; 106 } 107 } else { 108 cout << "NO" << endl; 109 } 110 } 111 112 }