Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- #define mp make_pair
- using namespace std;
- typedef long long ll;
- typedef pair <ll, ll> pii;
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
- const int INF = 1e7;
- const ll llINF = 1e17;
- const int mxN = 2e5 + 9;
- const int mxM = 1e5 + 9;
- const int MOD = 1e9 + 7;
- const double pi = acos (-1);
- int rand(int x, int y) {
- static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- return uniform_int_distribution<int>(x, y)(rng);
- }
- void setIO (string s) {
- freopen ((s + ".in").c_str(), "r", stdin);
- freopen ((s + ".out").c_str(), "w", stdout);
- return;
- }
- int n, m, p;
- string getS (ll x) {
- string s = "";
- for (int i = 0; i < m; i++)
- s += ((1 << i) & x) ? "1" : "0";
- return s;
- }
- void solve () {
- cin >> n >> m >> p;
- vector <ll> mask (n + 1, 0);
- for (int i = 1; i <= n; i++) {
- string s;
- cin >> s;
- for (int j = 0; j < (int) s.length(); j++) {
- if (s[j] == '1')
- mask[i] |= (1 << j);
- }
- }
- ll res = 0;
- for (int rep = 0; rep < 50; rep++) {
- ll x = mask[rand (1, n)];
- vector <ll> tmpMask (n + 1, 0);
- for (int i = 1; i <= n; i++) {
- int k = 0;
- for (int j = 0; j < m; j++) {
- if ((x & (1 << j)) == 0)
- continue;
- if (mask[i] & (1 << j))
- tmpMask[i] |= (1 << k);
- k++;
- }
- }
- vector <int> sup (1 << (p + 1), 0);
- for (int i = 1; i <= n; i++)
- sup[tmpMask[i]]++;
- for (int i = 0; i < p; i++) {
- for (int msk = 0; msk < (1 << i); msk++) {
- if ((msk & (1 << i)) == 0)
- sup[msk] += sup[msk ^ (1 << i)];
- }
- }
- ll best = 0;
- for (int y = x; y > 0; y = (y - 1) & x) {
- if (sup[y] >= ((n + 1) / 2) && __builtin_popcount(y) > __builtin_popcount(best)) {
- best = y;
- }
- }
- int k = 0;
- ll unCompressed = 0;
- for (int i = 0; i < m; i++) {
- if ((x & (1 << i)) == 0)
- continue;
- if ((1 << k) & best)
- unCompressed |= (1 << i);
- k++;
- }
- if (__builtin_popcount(unCompressed) > __builtin_popcount (res))
- res = unCompressed;
- }
- cout << getS(res) << "\n";
- return;
- }
- int main () {
- int t = 1;
- //cin >> t;
- //ios_base::sync_with_stdio (0);
- //cin.tie (0);
- //setIO ("billboard");
- //preCalc ();
- while (t--) {
- //initialize common variables
- //go solve
- solve ();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement