josephus_problem_ii.cpp (906B)
1 #include <bits/stdc++.h> 2 #include <ext/pb_ds/assoc_container.hpp> 3 #include <ext/pb_ds/tree_policy.hpp> 4 using namespace std; 5 using namespace __gnu_pbds; 6 7 template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 8 9 10 using ui = unsigned int; 11 using l = long; 12 using ul = unsigned long; 13 using ll = long long; 14 using ull = unsigned long long; 15 16 using vi = vector<int>; 17 using vui = vector<ui>; 18 using vl = vector<l>; 19 using vul = vector<ul>; 20 using vll = vector<ll>; 21 using vull = vector<ull>; 22 23 void solve() 24 { 25 l n, k; 26 cin >> n >> k; 27 ordered_set<int> res; 28 for (l i = 1; i <= n; i++) { 29 res.insert(i); 30 } 31 32 auto last = res.begin(); 33 int p = 0; 34 for (l i = 1; i <= n; i++) { 35 p = (p + k) % res.size(); 36 last = res.find_by_order(p); 37 cout << *last << " "; 38 res.erase(last); 39 } 40 cout << "\n"; 41 } 42 43 int main() 44 { 45 ios::sync_with_stdio(0); 46 cin.tie(0); 47 solve(); 48 }