#include <iostream> #include <queue> // #define DEBUG_M #ifdef DEBUG_M #define DEBUGF(...) fprintf(stderr, __VA_ARGS__) #define DEBUG(expr) expr #else #define DEBUGF(...) #define DEBUG(expr) #endif using namespace std; int simulate(priority_queue<int> &mids, priority_queue<int> &sides) { int time = 0; int saved = 0; for (;;) { if (mids.empty() && sides.empty()) { break; } else if (mids.empty() && !sides.empty()) { int willSave = sides.top() - time; if (willSave > 0) { saved += willSave; time++; sides.pop(); } else { break; } } else if (/* !mids.empty() && */ sides.empty()) { int midsSize = mids.top() - 2*time; if (midsSize <= 0) { break; } else if (midsSize == 1) { saved++; time++; } else { saved += midsSize - 1; time += 2; } mids.pop(); } else /* if (!mids.empty && !sides.empty()) */ { int midsSize = mids.top() - 2*time; int willSaveMids; int timeMids; if (midsSize > 1) { willSaveMids = midsSize-1; timeMids = 2; } else if (midsSize == 1) { willSaveMids = 1; timeMids = 1; } else { willSaveMids = -1; timeMids = 2; // Should never be used } int willSaveSides = sides.top() - time; DEBUGF("t: %d; m.t: %d; mS: %d; wSM: %d; tM: %d; s.t: %d; wSS: %d;\n", time, mids.top(), midsSize, willSaveMids, timeMids, sides.top(), willSaveSides); if (willSaveSides <= 0 && willSaveMids <= 0) { break; } else if (willSaveSides >= willSaveMids) { saved += willSaveSides; time++; sides.pop(); } else { saved += willSaveMids; time += timeMids; mids.pop(); } } } return saved; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; for (;t--;) { int n; cin >> n; string str; cin >> str; int sizeBegin = 0; int sizeEnd = 0; priority_queue<int> mids; int idx = 0; for (;str[idx] == '0' && idx < n; idx++); sizeBegin = idx; if (idx++ == n) { // Nie ma żadnych jedynek puts("0"); continue; } for(; idx < n; idx++) { if (str[idx] == '1') { if (sizeEnd) { mids.push(sizeEnd); sizeEnd = 0; } } else { sizeEnd++; } } priority_queue<int> sides; if (sizeBegin == sizeEnd && sizeBegin) { // BODGED EDGE CASE mids.push(2*sizeBegin); } else { if (sizeBegin) sides.push(sizeBegin); if (sizeEnd) sides.push(sizeEnd); } #ifdef DEBUG_M { auto tmp = mids; fprintf(stderr, "mids: "); for (;tmp.size();) { fprintf(stderr, "%d ", tmp.top()); tmp.pop(); } } { auto tmp = sides; fprintf(stderr, "\nsides: "); for (;tmp.size();) { fprintf(stderr, "%d ", tmp.top()); tmp.pop(); } } putc('\n', stderr); #endif int saved = simulate(mids, sides); DEBUGF("saved: %d\n", saved); printf("%d\n", n - saved); } }
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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | #include <iostream> #include <queue> // #define DEBUG_M #ifdef DEBUG_M #define DEBUGF(...) fprintf(stderr, __VA_ARGS__) #define DEBUG(expr) expr #else #define DEBUGF(...) #define DEBUG(expr) #endif using namespace std; int simulate(priority_queue<int> &mids, priority_queue<int> &sides) { int time = 0; int saved = 0; for (;;) { if (mids.empty() && sides.empty()) { break; } else if (mids.empty() && !sides.empty()) { int willSave = sides.top() - time; if (willSave > 0) { saved += willSave; time++; sides.pop(); } else { break; } } else if (/* !mids.empty() && */ sides.empty()) { int midsSize = mids.top() - 2*time; if (midsSize <= 0) { break; } else if (midsSize == 1) { saved++; time++; } else { saved += midsSize - 1; time += 2; } mids.pop(); } else /* if (!mids.empty && !sides.empty()) */ { int midsSize = mids.top() - 2*time; int willSaveMids; int timeMids; if (midsSize > 1) { willSaveMids = midsSize-1; timeMids = 2; } else if (midsSize == 1) { willSaveMids = 1; timeMids = 1; } else { willSaveMids = -1; timeMids = 2; // Should never be used } int willSaveSides = sides.top() - time; DEBUGF("t: %d; m.t: %d; mS: %d; wSM: %d; tM: %d; s.t: %d; wSS: %d;\n", time, mids.top(), midsSize, willSaveMids, timeMids, sides.top(), willSaveSides); if (willSaveSides <= 0 && willSaveMids <= 0) { break; } else if (willSaveSides >= willSaveMids) { saved += willSaveSides; time++; sides.pop(); } else { saved += willSaveMids; time += timeMids; mids.pop(); } } } return saved; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; for (;t--;) { int n; cin >> n; string str; cin >> str; int sizeBegin = 0; int sizeEnd = 0; priority_queue<int> mids; int idx = 0; for (;str[idx] == '0' && idx < n; idx++); sizeBegin = idx; if (idx++ == n) { // Nie ma żadnych jedynek puts("0"); continue; } for(; idx < n; idx++) { if (str[idx] == '1') { if (sizeEnd) { mids.push(sizeEnd); sizeEnd = 0; } } else { sizeEnd++; } } priority_queue<int> sides; if (sizeBegin == sizeEnd && sizeBegin) { // BODGED EDGE CASE mids.push(2*sizeBegin); } else { if (sizeBegin) sides.push(sizeBegin); if (sizeEnd) sides.push(sizeEnd); } #ifdef DEBUG_M { auto tmp = mids; fprintf(stderr, "mids: "); for (;tmp.size();) { fprintf(stderr, "%d ", tmp.top()); tmp.pop(); } } { auto tmp = sides; fprintf(stderr, "\nsides: "); for (;tmp.size();) { fprintf(stderr, "%d ", tmp.top()); tmp.pop(); } } putc('\n', stderr); #endif int saved = simulate(mids, sides); DEBUGF("saved: %d\n", saved); printf("%d\n", n - saved); } } |