main.cpp (2107B)
1 #include <iostream> 2 #include <cmath> 3 #include <vector> 4 #include <unordered_set> 5 #include <unordered_map> 6 #include <algorithm> 7 #include <queue> 8 9 #define ll long long 10 11 using namespace std; 12 13 // start from the beginning, fill with 1's until we reach ceil(k / 2), fill with 0's until we reach k total pairs, alternating on the rest 14 15 bool isValid(string st, int n, int k) { 16 int numZ = 0; 17 int numO = 0; 18 int numPairs = 0; 19 20 for(int i = 0; i < st.size(); ++i) { 21 if(i > 0) { 22 if(st[i] == st[i-1]) { 23 numPairs += 1; 24 } 25 } 26 if(st[i] == '1') { 27 numO += 1; 28 } else { 29 numZ += 1; 30 } 31 } 32 33 if(numPairs == k && abs(numZ-numO) <= 1 && st.size() == n) { 34 return true; 35 } 36 return false; 37 38 } 39 40 41 // THIS IS BAD: 110101 42 // THIS IS BAD: 6 43 // THIS IS BAD: 1 44 // this case has an issue. 45 46 // we want a prefix of a singular zero before our 1's otherwise we have too many 1's 47 // 011010 48 // can we just try both approaches? 49 // like just try prefixing with a zero if we fail once? 50 51 52 string generate(string bs, int n,int k) { 53 54 // we do +1 here because 11 is two characters but only one pair 55 int tgOne = (ceil((double)k / (double)2)) + 1; 56 int tgZero = (floor((double)k / (double)2)) + 1; 57 58 bool lastIsOne = false; 59 60 for(int i = 0; i < tgOne; ++i) { 61 bs += '1'; 62 } 63 for(int i = 0; i < tgZero; ++i) { 64 bs += '0'; 65 } 66 while(bs.size() < n) { 67 char last = bs[bs.size() - 1]; 68 if (last == '1') { 69 bs += '0'; 70 } else { 71 bs += '1'; 72 } 73 } 74 return bs; 75 } 76 77 78 int main() { 79 80 int testCases, n, k; 81 cin >> testCases; 82 83 for(int z = 0; z < testCases; ++z) { 84 cin >> n; 85 cin >> k; 86 87 string bs = generate("",n,k); 88 89 if(isValid(bs, n, k)) { 90 cout << bs << endl; 91 } else { 92 string bsT = generate("0",n,k); 93 if(isValid(bsT, n, k)) { 94 cout << bsT << endl; 95 } else { 96 cout << "-1" << endl; 97 } 98 } 99 } 100 }