fork download
copy 
  1. #ifdef ONPC
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4. #include <bits/stdc++.h>
  5. #define pii pair<int, int>
  6. using namespace std;
  7.  
  8. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  9. struct custom_hash
  10. {
  11.     static uint64_t splitmix64(uint64_t x)
  12.     {
  13.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  14.         x += 0x9e3779b97f4a7c15;
  15.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  16.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  17.         return x ^ (x >> 31);
  18.     }
  19.  
  20.     size_t operator()(uint64_t x) const
  21.     {
  22.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  23.         return splitmix64(x + FIXED_RANDOM);
  24.     }
  25. };
  26. void solve()
  27. {
  28.     int n, k, m, s;
  29.     cin >> n >> k >> m >> s;
  30.     vector<int> vis(n, 0);
  31.     s -= 1;
  32.     vis[s] = 1;
  33.     vector<set<int>> parity(2);
  34.     for (int i = 0; i < n; ++i)
  35.     {
  36.         parity[i % 2].insert(i);
  37.     }
  38.     parity[s % 2].erase(s);
  39.     for (int i = 0; i < m; ++i)
  40.     {
  41.         int x;
  42.         cin >> x;
  43.         --x;
  44.         parity[x % 2].erase(x);
  45.     }
  46.     vector<int> dist(n, -1);
  47.     dist[s] = 0;
  48.     queue<int> qu;
  49.     qu.push(s);
  50.     while (!qu.empty())
  51.     {
  52.         int curr = qu.front();
  53.         qu.pop();
  54.         vis[curr] = 1;
  55.         // ab curr say kidhar jaa sakte hain
  56.         int l__ = max(0, curr - k + 1);
  57.         int r__ = l__ + k - 1;
  58.         int mini = l__ + r__ - curr;
  59.         int r_ = min(n - 1, curr + k - 1);
  60.         int l_ = r_ - k + 1;
  61.         int maxi = r_ + l_ - curr;
  62.         //  cout << mini << ' ' << maxi << ' ';
  63.         auto it = parity[mini % 2].lower_bound(mini);
  64.         unordered_map<int, int, custom_hash> mp;
  65.         // cout << "Curr: " << curr << ' ';
  66.         while (it != parity[mini % 2].end() && *it <= maxi)
  67.         {
  68.             // cout << *it << ' ';
  69.             if (vis[*it] == 0 || dist[*it] > dist[curr] + 1)
  70.             {
  71.                 dist[*it] = dist[curr] + 1;
  72.                 qu.push(*it);
  73.                 mp[*it] = 1;
  74.             }
  75.             it++;
  76.             // because hum idhar ponch gaye hains
  77.         }
  78.         // cout << endl;
  79.         for (auto [x, y] : mp)
  80.         {
  81.             parity[x % 2].erase(x);
  82.         }
  83.     }
  84.     for (auto i : dist)
  85.     {
  86.         cout << i << ' ';
  87.     }
  88.     return;
  89. }
  90.  
  91. signed main()
  92. {
  93.     ios::sync_with_stdio(0);
  94.     cin.tie(0);
  95.     int t = 1;
  96. #ifdef ONPC
  97.     freopen("input.txt", "r", stdin);
  98. #endif
  99.     // cin >> t;
  100.     for (int i = 0; i < t; ++i)
  101.     {
  102.         solve();
  103.     }
  104. #ifdef ONPC
  105.     cerr << endl
  106.          << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  107. #endif
  108.     return 0;
  109. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
10 4 3 3
2 5 10
stdout
copy 
2 -1 0 1 -1 1 2 3 2 -1
https://ideone.com/yNjbKQ
language:
C++14 (gcc 8.3)
created:
19 hours 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!