fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=1e9+7;
  49. const int maxn=3e5+15;
  50. const ll inf=2e18;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71.  
  72. static inline bool has2(const vector<uint64_t>& A, const vector<uint64_t>& B){
  73.     bool one = false;
  74.     for(size_t k = 0; k < A.size(); ++k){
  75.         uint64_t x = A[k] & B[k];
  76.         if(!x) continue;
  77.         if (x & (x - 1)) return true;
  78.         if (one) return true;
  79.         one = true;
  80.     }
  81.     return false;
  82. }
  83.  
  84. int main(){
  85.     rf();
  86.     int m, n;
  87.     if(!(cin >> m >> n)) return 0;
  88.     vector<vector<long long>> a(m, vector<long long>(n));
  89.     for(int i = 0; i < m; ++i)
  90.         for(int j = 0; j < n; ++j)
  91.             cin >> a[i][j];
  92.  
  93.     if(m > n){
  94.         vector<vector<long long>> t(n, vector<long long>(m));
  95.         for(int i = 0; i < m; ++i)
  96.             for(int j = 0; j < n; ++j)
  97.                 t[j][i] = a[i][j];
  98.         a.swap(t);
  99.         swap(m, n);
  100.     }
  101.  
  102.     vector<long long> vals;
  103.     vals.reserve((size_t)m * n);
  104.     for(int i = 0; i < m; ++i)
  105.         for(int j = 0; j < n; ++j)
  106.             vals.push_back(a[i][j]);
  107.     sort(vals.begin(), vals.end());
  108.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  109.  
  110.     auto ok = [&](long long T)->bool{
  111.         int chunks = (n + 63) >> 6;
  112.         vector<vector<uint64_t>> row(m, vector<uint64_t>(chunks));
  113.         for(int i = 0; i < m; ++i){
  114.             for(int j = 0; j < n; ++j){
  115.                 if(a[i][j] >= T){
  116.                     int idx = j >> 6, off = j & 63;
  117.                     row[i][idx] |= (uint64_t(1) << off);
  118.                 }
  119.             }
  120.         }
  121.         for(int i = 0; i < m; ++i)
  122.             for(int j = i + 1; j < m; ++j)
  123.                 if(has2(row[i], row[j])) return true;
  124.         return false;
  125.     };
  126.  
  127.     int lo = 0, hi = (int)vals.size() - 1;
  128.     while(lo < hi){
  129.         int mid = (lo + hi + 1) >> 1;
  130.         if(ok(vals[mid])) lo = mid; else hi = mid - 1;
  131.     }
  132.     cout << vals[lo] << '\n';
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
stdout
copy 
11
https://ideone.com/1883hk
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

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!