fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. bool func(ll mid, vector<vector<ll>> &V, ll r)
  6. {
  7.     map<ll, ll> mt;
  8.     ll cnt = 0;
  9.     vector<pair<ll, map<ll, ll>>> mp(V[0].size(), {0, mt});
  10.     for (ll i = 0; i < mid; i++)
  11.     {
  12.         for (ll j = 0; j < V[0].size(); j++)
  13.         {
  14.             ll d = V[i][j];
  15.             ll ct = 0;
  16.             while (d > 0)
  17.             {
  18.                 ll k = d % 2;
  19.                 if (k == 1)
  20.                 {
  21.                     mp[j].second[ct]++;
  22.                     if (mp[j].second[ct] == 1)
  23.                     {
  24.                         mp[j].first = mp[j].first + (1 << ct);
  25.                     }
  26.                 }
  27.                 d = d / 2;
  28.                 ct++;
  29.             }
  30.         }
  31.     }
  32.     map<ll, ll> pm;
  33.     ll ans = 0;
  34.     for (ll i = 0; i < mid; i++)
  35.     {
  36.         ll s = mp[i].first;
  37.         ll ct = 0;
  38.         while (s > 0)
  39.         {
  40.             ll k = s % 2;
  41.             if (k == 1)
  42.             {
  43.                 pm[ct]++;
  44.                 if (pm[ct] == 1)
  45.                 {
  46.                     ans = ans + (1 << ct);
  47.                 }
  48.             }
  49.             s = s / 2;
  50.             ct++;
  51.         }
  52.     }
  53.     if (ans > r)
  54.     {
  55.         cnt++;
  56.     }
  57.  
  58.     ll j = 0;
  59.     for (ll i = mid; i < V[0].size(); i++)
  60.     {
  61.         ll t = mp[j].first;
  62.         ll ctt = 0;
  63.         while (t > 0)
  64.         {
  65.             ll k = t % 2;
  66.             if (k == 1)
  67.             {
  68.                 pm[ctt]--;
  69.                 if (pm[ctt] == 0)
  70.                 {
  71.                     ans = ans - (1 << ctt);
  72.                 }
  73.             }
  74.             ctt++;
  75.             t = t / 2;
  76.         }
  77.         ll s = mp[i].first;
  78.         ll ct = 0;
  79.         while (s > 0)
  80.         {
  81.             ll k = s % 2;
  82.             if (k == 1)
  83.             {
  84.                 pm[ct]++;
  85.                 if (pm[ct] == 1)
  86.                 {
  87.                     ans = ans + (1 << ct);
  88.                 }
  89.             }
  90.             s = s / 2;
  91.             ct++;
  92.         }
  93.         j++;
  94.         if (ans > r)
  95.         {
  96.             cnt++;
  97.         }
  98.     }
  99.     ll l = 0;
  100.     for (ll i = mid; i < V.size(); i++)
  101.     {
  102.         for (ll j = 0; j < V[0].size(); j++)
  103.         {
  104.             ll e = V[l][j];
  105.             ll ctt = 0;
  106.             while (e > 0)
  107.             {
  108.                 ll k = e % 2;
  109.                 if (k == 1)
  110.                 {
  111.                     mp[j].second[ctt]--;
  112.                     if (mp[j].second[ctt] == 0)
  113.                     {
  114.                         mp[j].first = mp[j].first - (1 << ctt);
  115.                     }
  116.                 }
  117.                 e = e / 2;
  118.                 ctt++;
  119.             }
  120.             ll d = V[i][j];
  121.             ll ct = 0;
  122.             while (d > 0)
  123.             {
  124.                 ll k = d % 2;
  125.                 if (k == 1)
  126.                 {
  127.                     mp[j].second[ct]++;
  128.                     if (mp[j].second[ct] == 1)
  129.                     {
  130.                         mp[j].first = mp[j].first + (1 << ct);
  131.                     }
  132.                 }
  133.                 d = d / 2;
  134.                 ct++;
  135.             }
  136.         }
  137.  
  138.         map<ll, ll> pmm;
  139.         ans = 0;
  140.         for (ll i1 = 0; i1 < mid; i1++)
  141.         {
  142.             ll s1 = mp[i1].first;
  143.             ll ct1 = 0;
  144.             while (s1 > 0)
  145.             {
  146.                 ll k1 = s1 % 2;
  147.                 if (k1 == 1)
  148.                 {
  149.                     pmm[ct1]++;
  150.                     if (pmm[ct1] == 1)
  151.                     {
  152.                         ans = ans + (1 << ct1);
  153.                     }
  154.                 }
  155.                 s1 = s1 / 2;
  156.                 ct1++;
  157.             }
  158.         }
  159.         if (ans > r)
  160.         {
  161.             cnt++;
  162.         }
  163.         ll j1 = 0;
  164.         for (ll i1 = mid; i1 < V[0].size(); i1++)
  165.         {
  166.             ll t1 = mp[j1].first;
  167.             ll ctt1 = 0;
  168.             while (t1 > 0)
  169.             {
  170.                 ll k1 = t1 % 2;
  171.                 if (k1 == 1)
  172.                 {
  173.                     pmm[ctt1]--;
  174.                     if (pmm[ctt1] == 0)
  175.                     {
  176.                         ans = ans - (1 << ctt1);
  177.                     }
  178.                 }
  179.                 ctt1++;
  180.                 t1 = t1 / 2;
  181.             }
  182.             ll s1 = mp[i1].first;
  183.             ll ct1 = 0;
  184.             while (s1 > 0)
  185.             {
  186.                 ll k1 = s1 % 2;
  187.                 if (k1 == 1)
  188.                 {
  189.                     pmm[ct1]++;
  190.                     if (pmm[ct1] == 1)
  191.                     {
  192.                         ans = ans + (1 << ct1);
  193.                     }
  194.                 }
  195.                 s1 = s1 / 2;
  196.                 ct1++;
  197.             }
  198.             j1++;
  199.             if (ans > r)
  200.             {
  201.                 cnt++;
  202.             }
  203.         }
  204.             l++;
  205.     }
  206.     return cnt > 0;
  207. }
  208.  
  209. int main()
  210. {
  211.     ll n, m, r;
  212.     cin >> n >> m >> r;
  213.     vector<vector<ll>> V(n, vector<ll>(m));
  214.     for (ll i = 0; i < n; i++)
  215.     {
  216.         for (ll j = 0; j < m; j++)
  217.         {
  218.             cin >> V[i][j];
  219.         }
  220.     }
  221.     ll low = 1, high = min(n, m);
  222.     while (high - low > 1)
  223.     {
  224.         ll mid = (low + high) / 2;
  225.         if (func(mid, V, r))
  226.         {
  227.             high = mid;
  228.         }
  229.         else
  230.         {
  231.             low = mid + 1;
  232.         }
  233.  
  234.     }
  235.     if (func(low, V, r))
  236.     {
  237.         cout << low << endl;
  238.     }
  239.     else if (func(high, V, r))
  240.     {
  241.         cout << high << endl;
  242.     }
  243.     else
  244.     {
  245.         cout << -1 << endl;
  246.     }
  247.     return 0;
  248. }
Runtime error #stdin #stdout #stderr 0.01s 5440KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/LPpOqB
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!