fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty
stderr
  File "prog.py", line 131
    (pot >= k+same)? h=m : (l=m+1, ans = l);
                   ^
SyntaxError: Unknown character