fork download
copy 
  1. // Mochi Kasato - MKasato
  2. // FB: facebook.com/mochikasato/
  3. // Problem link:
  4. #include <bits/stdc++.h>
  5. #define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
  6. #define openf if (fopen("test.inp", "r")) {freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);}
  7. #define fi first
  8. #define se second
  9. #define pb(x) push_back(x)
  10.  
  11. using namespace std;
  12. typedef long long ll;
  13. typedef pair<int, int> pii;
  14.  
  15. int n;
  16. int q;
  17. ll c;
  18. int x, y;
  19.  
  20. pair<int, int> tim(int x1, int y1, int x2, int y2, ll l, ll r) {
  21.     if (l == r) {
  22.         return make_pair(x1, y1);
  23.     }
  24.     ll len = (r-l+1)/4;
  25.     int midx = x1 + x2;
  26.     int midy = y1 + y2;
  27.     if (l<=c && c<=l+len-1) return tim(x1, y1, (midx-1)/2, (midy-1)/2, l, l+len-1);
  28.     if (l+len<=c && c<=l+len*2-1) return tim(x1, (midy+1)/2, (midx-1)/2, y2, l+len, l+len*2-1);
  29.     if (l+len*2<=c && c<=l+len*3-1) return tim((midx+1)/2, (midy+1)/2, x2, y2, l+len*2, l+len*3-1);
  30.     if (l+len*3<=c && c<=r) return tim((midx+1)/2, y1, x2, (midy-1)/2, l+len*3, r);
  31. }
  32. ll loaicay(int x1, int y1, int x2, int y2, ll l, ll r) {
  33.     if (x1==x2 && y1==y2) {
  34.         return l;
  35.     }
  36.     ll len = (r-l+1)/4;
  37.     int midx = x1 + x2;
  38.     int midy = y1 + y2;
  39.     if (x1<=x && x<=(midx-1)/2 &&
  40.         y1<=y && y<=(midy-1)/2) return loaicay(x1, y1, (midx-1)/2, (midy-1)/2, l, l+len-1);
  41.  
  42.     if (x1<=x && x<=(midx-1)/2 &&
  43.         (midy+1)/2<=y && y<=y2) return loaicay(x1, (midy+1)/2, (midx-1)/2, y2, l+len, l+len*2-1);
  44.  
  45.     if ((midx+1)/2<=x && x<=x2 &&
  46.         (midy+1)/2<=y && y<=y2) return loaicay((midx+1)/2, (midy+1)/2, x2, y2, l+len*2, l+len*3-1);
  47.  
  48.     if ((midx+1)/2<=x && x<=x2 &&
  49.         y1<=y && y<=(midy-1)/2) return loaicay((midx+1)/2, y1, x2, (midy-1)/2, l+len*3, r);
  50. }
  51.  
  52. int main() {
  53.     boostcode;
  54. //    openf;
  55.  
  56.     cin >> n;
  57.     cin >> q;
  58.     const ll N2 = (ll)n*n;
  59.     for (int i = 1; i <= q; i++) {
  60.         int op;
  61.         cin >> op;
  62.         if (op == 1) {
  63.             cin >> c;
  64.             pair<int, int> res = tim(1, 1, n, n, 1, N2);
  65.             cout << res.fi << ' ' << res.se << '\n';
  66.         } else { // op == 2:
  67.             cin >> x >> y;
  68.             cout << loaicay(1, 1, n, n, 1, N2) << '\n';
  69.         }
  70.     }
  71.  
  72.     return 0;
  73. }
  74. /* TESTS:
  75. Test 1:
  76. 4
  77. 2
  78. 2 3 4
  79. 1 8
  80. -->
  81. 10
  82. 2 3
  83. Test 2:
  84. 8
  85. 4
  86. 1 4
  87. 2 3 4
  88. 1 15
  89. 2 5 7
  90. -->
  91. 2 1
  92. 10
  93. 4 2
  94. 37
  95. */
  96.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
8
4
1 4
2 3 4
1 15
2 5 7
stdout
copy 
2 1
10
4 2
37
https://ideone.com/9ShISu
language:
C++14 (gcc 8.3)
created:
47 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!