fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. // 獲取數字 X 在 S 序列中的位置 P
  6. int findPosition(int N, int X) {
  7.     int row = X / N, col = X % N;
  8.     int pos = 0;
  9.  
  10.     for (int size = N; size > 1; size /= 2) {
  11.         int half = size / 2;
  12.         if (row >= half) { // 垂直折疊
  13.             row = size - row - 1;
  14.             pos += half * half;
  15.         }
  16.         if (col >= half) { // 水平折疊
  17.             col = size - col - 1;
  18.             pos += half * half;
  19.         }
  20.     }
  21.     return pos + 1; // 轉為 1-based index
  22. }
  23.  
  24. // 獲取序列位置 P 的數字 X
  25. int findNumber(int N, int P) {
  26.     int row = 0, col = 0;
  27.     int pos = P - 1; // 轉為 0-based index
  28.  
  29.     for (int size = 1; size < N; size *= 2) {
  30.         int half = size;
  31.         if (pos >= half * half * 2) {
  32.             pos -= half * half * 2;
  33.             col += half;
  34.         }
  35.         if (pos >= half * half) {
  36.             pos -= half * half;
  37.             row += half;
  38.         }
  39.     }
  40.     return row * N + col;
  41. }
  42.  
  43. int main() {
  44.     int N, Q, type, value, k;
  45.     cin >> Q; // 讀取 N 與查詢數量 Q
  46.     while (Q--) {
  47.         cin >> type >> k >> value;
  48.         N = 1 << k;
  49.         if (type == 2) {
  50.             cout << findPosition(N, value) << endl;
  51.         } else {
  52.             cout << findNumber(N, value) << endl;
  53.         }
  54.     }
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
1 1 4
2 2 14
1 2 16
stdout
copy 
3
10
15
https://ideone.com/T9baMZ
language:
C++14 (gcc 8.3)
created:
2 days 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!