fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. struct Interval {
  9.     int l, r;
  10.     int dist;
  11.     int mid;
  12.  
  13.     bool operator<(const Interval& other) const {
  14.         if (dist != other.dist) return dist > other.dist;
  15.         return mid < other.mid;
  16.     }
  17. };
  18.  
  19. int N, A, B;
  20.  
  21. vector<int> simulate(int start) {
  22.     vector<int> res;
  23.     vector<bool> hit(N + 2, false);
  24.     hit[0] = hit[N + 1] = true;
  25.  
  26.     res.push_back(start);
  27.     hit[start] = true;
  28.  
  29.     set<Interval> q;
  30.     if (start > 1) q.insert({1, start - 1, (start - 1) / 2, (1 + start - 1) / 2});
  31.     if (start < N) q.insert({start + 1, N, (N - (start + 1)) / 2, (start + 1 + N) / 2});
  32.  
  33.     while (!q.empty()) {
  34.         Interval best_int = *q.begin();
  35.         int cand_pq = best_int.mid;
  36.         int dist_pq = best_int.dist;
  37.  
  38.         int cand_1 = -1, dist_1 = -1;
  39.         if (!hit[1]) {
  40.             int r = 1;
  41.             while (r <= N && !hit[r]) r++;
  42.             cand_1 = 1;
  43.             dist_1 = r - 2;
  44.         }
  45.  
  46.         int cand_N = -1, dist_N = -1;
  47.         if (!hit[N]) {
  48.             int l = N;
  49.             while (l >= 1 && !hit[l]) l--;
  50.             cand_N = N;
  51.             dist_N = N - l - 1;
  52.         }
  53.  
  54.         int max_d = max({dist_pq, dist_1, dist_N});
  55.         int best_pos = 1e9;
  56.  
  57.         if (dist_1 == max_d) best_pos = min(best_pos, cand_1);
  58.         if (dist_N == max_d) best_pos = min(best_pos, cand_N);
  59.         if (dist_pq == max_d) best_pos = min(best_pos, cand_pq);
  60.  
  61.         res.push_back(best_pos);
  62.         hit[best_pos] = true;
  63.  
  64.         if (best_pos == cand_pq) {
  65.             q.erase(q.begin());
  66.             if (best_pos > best_int.l) 
  67.                 q.insert({best_int.l, best_pos - 1, (best_pos - 1 - best_int.l) / 2, (best_int.l + best_pos - 1) / 2});
  68.             if (best_pos < best_int.r) 
  69.                 q.insert({best_pos + 1, best_int.r, (best_int.r - (best_pos + 1)) / 2, (best_pos + 1 + best_int.r) / 2});
  70.         } else {
  71.             set<Interval> next_q;
  72.             for (auto it : q) {
  73.                 if (best_pos >= it.l && best_pos <= it.r) {
  74.                     if (best_pos > it.l) 
  75.                         next_q.insert({it.l, best_pos - 1, (best_pos - 1 - it.l) / 2, (it.l + best_pos - 1) / 2});
  76.                     if (best_pos < it.r) 
  77.                         next_q.insert({best_pos + 1, it.r, (it.r - (best_pos + 1)) / 2, (best_pos + 1 + it.r) / 2});
  78.                 } else {
  79.                     next_q.insert(it);
  80.                 }
  81.             }
  82.             q = next_q;
  83.         }
  84.     }
  85.  
  86.     return res;
  87. }
  88.  
  89. int main() {
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(NULL);
  92.  
  93.     if (!(cin >> N >> A >> B)) return 0;
  94.  
  95.     for (int s = 1; s <= N; ++s) {
  96.         vector<int> path = simulate(s);
  97.         if (path.size() >= (size_t)A && path[A - 1] == B) {
  98.             for (int i = 0; i < N; ++i) {
  99.                 cout << path[i] << (i == N - 1 ? "" : " ");
  100.             }
  101.             cout << endl;
  102.             return 0;
  103.         }
  104.     }
  105.  
  106.     cout << -1 << endl;
  107.     return 0;
  108. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CUGs1U
language:
C++14 (gcc 8.3)
created:
1 day 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!