1360H - Binary Median - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
typedef pair<int, string> PIS;
typedef pair<double, double> PDD;
const double eps = 1e-9;
const int N = 3e5 + 10, M = 6e5 + 10, P = 998244353, INF = 0x3f3f3f3f;

int n, m;
set<ll> s;

void solve()
{
    s.clear();
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        string a;
        ll tmp = 0;
        cin >> a;
        for (int j = 0; j < m; j++)
        {
            tmp <<= 1;
            tmp += a[j] - '0';
        }
        s.insert(tmp);
    }
    ll res = ((1ll << m) - n - 1) / 2;
    for (auto i : s)
    {
        if (i <= res)
        {
            res++;
        }
    }
    for (int i = m - 1; i >= 0; i--)
    {
        cout << (int)((res >> i) & 1);
    }
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}