fork download
copy 
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4. #pragma GCC optimize("O2", "unroll-loops", "inline", "-ffast-math")
  5. #pragma GCC target("avx,sse2,sse3,sse4,mmx")
  6. using namespace std;
  7. #define fastio ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  8. #define ll long long
  9. #define int ll
  10. #define ld long double
  11. #define eps 1e-12
  12. #define MOD ((int)1e9+7)
  13. int sqr(int x) {
  14.     int l(0), r(x);
  15.     int a(x), b((x + 1) >> 1);
  16.     while (a > b)
  17.         a = b, b = (b + x / b) >> 1;
  18.     return a;
  19. }
  20. namespace nCr
  21. {
  22.     int fastpo(int base, int exp) {
  23.         int ans = 1;
  24.         while(exp)
  25.         {
  26.             if(exp&1) ans = (1ll * ans * base) % MOD;
  27.             base = (1ll * base * base) % MOD;
  28.             exp >>= 1;
  29.         }
  30.         return ans;
  31.     }
  32.     vector<int> fac, inv, finv;
  33.     void sz(int n) {
  34.         fac.resize(n+3),inv.resize(n+3),finv.resize(n+3);
  35.         fac[0]=inv[0]=inv[1]=finv[0]=finv[1]=1;
  36.         for(int i(1); i<=n; ++i) fac[i]=fac[i-1]*i%MOD;
  37.         for(int i(2); i<=n; ++i) inv[i]=MOD-MOD/i*inv[MOD%i]%MOD;
  38.         for(int i(2); i<=n; ++i) finv[i]=finv[i-1]*inv[i]%MOD;
  39.     }
  40.     int C(int n, int r) {
  41.         if(n<0 or r>n) return 0;
  42.         return(fac[n]*finv[r]%MOD*finv[n-r]%MOD);
  43.     }
  44. }
  45. const int C = (1ll << 30) % MOD;
  46. struct FenwickTree {
  47.     int size;
  48.     vector<int> tree;
  49.     FenwickTree(int n) : size(n), tree(n+1) {}
  50.  
  51.     void add(int idx, int delta){
  52.         while (idx <= size){
  53.             tree[idx] += delta;
  54.             idx += idx & -idx;
  55.         }
  56.     }
  57.  
  58.     int query(int idx) const{
  59.         int res(0), i(idx);
  60.         while (i > 0)
  61.             res += tree[i], i -= i & -i;
  62.         return res;
  63.     }
  64.  
  65.     void reset(){
  66.         fill(tree.begin(), tree.end(), 0);
  67.     }
  68. };
  69.  
  70. void GETAC() {
  71.  
  72.     int n, k, c(0), m, q, r, x, f, ans(0);
  73.     int A, B, M, R, C;
  74.     cin >> R >> C >> k;
  75.     vector<vector<pair<int, int>>> vp;
  76.     int mxown(0);
  77.     vector<vector<int>> grid(R, vector<int>(C));
  78.     for(int i(0); i < R; ++i){
  79.         for(int j(0); j < C; ++j){
  80.             cin >> grid[i][j];
  81.             if(grid[i][j] > mxown)
  82.                 mxown = grid[i][j];
  83.         }
  84.     }
  85.     vp.assign(mxown+1, vector<pair<int, int>>());
  86.     for(int i(0); i < R; ++i){
  87.         for(int j(0), idx; j < C; ++j){
  88.             idx = grid[i][j],
  89.             vp[idx].emplace_back(make_pair(i+1, j+1));
  90.         }
  91.     }
  92.     vector<vector<pair<int, int>>> p(mxown);
  93.     for (int o(1); o <= mxown; ++o){
  94.         if (vp[o].size() > 1){
  95.             sort(vp[o].begin(), vp[o].end(), [&](const pair<int,int> &a, const pair<int,int> &b) -> bool{
  96.                 if(a.first ^ b.first) return a.first < b.first;
  97.                 else return a.second < b.second;
  98.             });
  99.             p.emplace_back(vp[o]);
  100.         }
  101.     }
  102.     int l(0), h(max(R, C));
  103.     while (l < h){
  104.         m = (l + ((h-l) >> 1));
  105.         int s(0);
  106.         for (int i(1), ai; i <= R; ++i){
  107.             ai = min(R, i+m) - max(1ll, i-m) + 1;
  108.             s += ai;
  109.         }
  110.         int sb(0);
  111.         for(int j(1), bj; j <= C; ++j){
  112.             bj = min(C, j + m) - max(1ll, j-m) + 1;
  113.             sb += bj;
  114.         }
  115.         int pot(s*sb - R*C), same(0);
  116.         FenwickTree ft(C);
  117.         for(auto &cell : p){
  118.             int n(cell.size()), l(0), r(0);
  119.             ft.reset();
  120.             for(int i(0); i < n; ++i){
  121.                 int curx(cell[i].first), cury(cell[i].second);
  122.                 while (r < n and cell[r].first <= curx+m)
  123.                     ft.add(cell[r].second, 1), ++r;
  124.                 while (l < n and cell[l].first < curx-m)
  125.                     ft.add(cell[l].second, -1), ++l;
  126.                 int cl(max(1ll, (int)(cury-m))), cr(min((int)C, (int)(cury+m))),
  127.                 f(ft.query(cr) - ft.query(cl-1));
  128.                 same += f-1;
  129.             }
  130.         }
  131.         (pot >= k+same)? h=m : (l=m+1, ans = l);
  132.     }
  133.     cout << ans;
  134. }
  135.  
  136.  
  137. static void run_with_stack_size(void (*func)(void), size_t stsize) {
  138.     char *stack, *send;
  139.     stack = (char *)malloc(stsize);
  140.     if (!stack) {
  141.         exit(1);
  142.     }
  143.     send = stack + stsize - 16;
  144.     send = (char *)((uintptr_t)send & -16L);
  145.  
  146.     asm volatile(
  147.             "mov %%rsp, (%0)\n"
  148.             "mov %0, %%rsp\n"
  149.             :
  150.             : "r"(send)
  151.             : "memory"
  152.             );
  153.  
  154.     func();
  155.  
  156.     asm volatile(
  157.             "mov (%0), %%rsp\n"
  158.             :
  159.             : "r"(send)
  160.             : "memory"
  161.             );
  162.  
  163.     free(stack);
  164. }
  165.  
  166. signed main() {
  167.     fastio
  168. freopen("D:\\META\\bunny_hopscotch_input.txt", "r", stdin);
  169.     freopen("D:\\META\\OUT1.txt", "w", stdout);
  170.     int T;
  171.     cin >> T;
  172.  
  173.     for (int tc(1); tc <= T; ++tc){
  174.         cout << "Case #" << tc << ": ";
  175.         run_with_stack_size(GETAC, 1024 * 1024 * 1024);
  176.         cout << "\n";
  177.     }
  178.  
  179.     return 0;
  180. }
  181.  
  182.  
Runtime error #stdin #stdout #stderr 0.06s 62892KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
  File "prog.py", line 131
    (pot >= k+same)? h=m : (l=m+1, ans = l);
                   ^
SyntaxError: Unknown character
https://ideone.com/fUH2DY
language:
Python (PyPy 2.7.13)
created:
37 days 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!