algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (1514B)


      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 // k defines how many characters can be swapped at the start
     13 // 
     14 
     15 int main() {
     16 
     17     int testCases, n, k;
     18     string s = "";
     19     cin >> testCases;
     20 
     21     for(int z = 0; z < testCases; ++z) {
     22         cin >> n;
     23         cin >> k;
     24         cin >> s;
     25 
     26         int zeroCount = 0;
     27         int oneCount = 0;
     28         for(int i = 0; i < n; ++i) {
     29             if(s[i] == '0') {
     30                 zeroCount += 1;
     31             } else {
     32                 oneCount += 1;
     33             }
     34         }
     35 
     36         int flipped = 0;
     37 
     38         if(zeroCount > oneCount) {
     39             for(int i = 0; i < n && flipped < k; ++i) {
     40                 if(s[i] == '1') {
     41                     s[i] = '0';
     42                     flipped += 1;
     43                     zeroCount += 1;
     44                     oneCount -= 1;
     45                 }
     46             }
     47         } else {
     48             for(int i = 0; i < n && flipped < k; ++i) {
     49                 if(s[i] == '0') {
     50                     s[i] = '1';
     51                     flipped += 1;
     52                     zeroCount -= 1;
     53                     oneCount += 1;
     54                 }
     55             }
     56         }
     57         
     58         long long res = 1;
     59 
     60         for(int i = 1; i <= zeroCount; ++i) {
     61             res += (zeroCount + 1) - i;
     62         }
     63         for(int i = 1; i <= oneCount; ++i) {
     64             res += (oneCount + 1) - i;
     65         }
     66         cout << res << '\n';
     67 
     68     }
     69 }