fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct Target {
  9.     int dist, id, l, r;
  10.     bool is_boundary;
  11.  
  12.     // Kolejka priorytetowa w C++ zwraca największy element.
  13.     // Chcemy: 1. Max dist, 2. Min ID.
  14.     bool operator<(const Target& other) const {
  15.         if (dist != other.dist) return dist < other.dist;
  16.         return id > other.id; 
  17.     }
  18. };
  19.  
  20. // Funkcja sprawdzająca, na której pozycji w sekwencji znajdzie się tarcza b dla danego x1
  21. int get_rank(int n, int x1, int b, int target_rank) {
  22.     if (x1 == b) return 1;
  23.  
  24.     priority_queue<Target> pq;
  25.     // Początkowe cele to brzegi (jeśli x1 nie jest brzegiem)
  26.     if (x1 > 1) pq.push({x1 - 1, 1, 1, x1, true});
  27.     if (x1 < n) pq.push({n - x1, n, x1, n, true});
  28.  
  29.     int current_rank = 1;
  30.     while (!pq.empty()) {
  31.         Target curr = pq.top();
  32.         pq.pop();
  33.  
  34.         current_rank++;
  35.         if (curr.id == b) return current_rank;
  36.         if (current_rank > target_rank) return -1; // Optymalizacja: b będzie później
  37.  
  38.         if (curr.is_boundary) {
  39.             // Jeśli trafiliśmy brzeg, tworzymy przedział zamknięty między nim a x1
  40.             int L = min(curr.id, curr.l == curr.id ? curr.r : curr.l);
  41.             int R = max(curr.id, curr.l == curr.id ? curr.r : curr.l);
  42.             if (R - L > 1) {
  43.                 int d = (R - L) / 2;
  44.                 pq.push({d, L + d, L, R, false});
  45.             }
  46.         } else {
  47.             // Podział przedziału zamkniętego [L, R] przez środek
  48.             int mid = curr.id;
  49.             // Lewa połowa [L, mid]
  50.             if (mid - curr.l > 1) {
  51.                 int d = (mid - curr.l) / 2;
  52.                 pq.push({d, curr.l + d, curr.l, mid, false});
  53.             }
  54.             // Prawa połowa [mid, R]
  55.             if (curr.r - mid > 1) {
  56.                 int d = (curr.r - mid) / 2;
  57.                 pq.push({d, mid + d, mid, curr.r, false});
  58.             }
  59.         }
  60.     }
  61.     return -1;
  62. }
  63.  
  64. int main() {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(NULL);
  67.  
  68.     int n, a, b;
  69.     if (!(cin >> n >> a >> b)) return 0;
  70.  
  71.     int found_x1 = -1;
  72.     // Szukamy najmniejszego x1, które spełnia warunek (leksykograficznie)
  73.     for (int x1 = 1; x1 <= n; ++x1) {
  74.         if (get_rank(n, x1, b, a) == a) {
  75.             found_x1 = x1;
  76.             break;
  77.         }
  78.     }
  79.  
  80.     if (found_x1 == -1) {
  81.         cout << "NIE" << endl;
  82.     } else {
  83.         // Odtwarzanie pełnej sekwencji dla znalezionego x1
  84.         vector<int> res;
  85.         res.push_back(found_x1);
  86.         priority_queue<Target> pq;
  87.  
  88.         if (found_x1 > 1) pq.push({found_x1 - 1, 1, 1, found_x1, true});
  89.         if (found_x1 < n) pq.push({n - found_x1, n, found_x1, n, true});
  90.  
  91.         while (!pq.empty()) {
  92.             Target curr = pq.top();
  93.             pq.pop();
  94.             res.push_back(curr.id);
  95.  
  96.             if (curr.is_boundary) {
  97.                 int L = min(curr.id, curr.l == curr.id ? curr.r : curr.l);
  98.                 int R = max(curr.id, curr.l == curr.id ? curr.r : curr.l);
  99.                 if (R - L > 1) {
  100.                     int d = (R - L) / 2;
  101.                     pq.push({d, L + d, L, R, false});
  102.                 }
  103.             } else {
  104.                 int mid = curr.id;
  105.                 if (mid - curr.l > 1) {
  106.                     int d = (mid - curr.l) / 2;
  107.                     pq.push({d, curr.l + d, curr.l, mid, false});
  108.                 }
  109.                 if (curr.r - mid > 1) {
  110.                     int d = (curr.r - mid) / 2;
  111.                     pq.push({d, mid + d, mid, curr.r, false});
  112.                 }
  113.             }
  114.         }
  115.  
  116.         for (int i = 0; i < n; ++i) {
  117.             cout << res[i] << (i == n - 1 ? "" : " ");
  118.         }
  119.         cout << endl;
  120.     }
  121.  
  122.     return 0;
  123. }
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin
copy 
4  3 2
stdout
copy 
1 4 2 3
https://ideone.com/voEGMS
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!