cses

commit fb8240fb0274fd51dde578eb31bff8a6ee414f63
parent 04af54b28c80829a2702adbbf1e91cb154a9dfed
Author: superpozycja <anna@superpozycja.net>
Date:   Wed, 30 Oct 2024 23:01:26 +0100

solve josephus problem ii

Diffstat:
A
sorting_and_searching/josephus_problem_ii.cpp
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 48 insertions(+), 0 deletions(-)
diff --git a/sorting_and_searching/josephus_problem_ii.cpp b/sorting_and_searching/josephus_problem_ii.cpp
@@ -0,0 +1,48 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+using namespace std;
+using namespace __gnu_pbds;
+
+template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
+
+
+using ui = unsigned int;
+using l = long;
+using ul = unsigned long;
+using ll = long long;
+using ull = unsigned long long;
+
+using vi = vector<int>;
+using vui = vector<ui>;
+using vl = vector<l>;
+using vul = vector<ul>;
+using vll = vector<ll>;
+using vull = vector<ull>;
+
+void solve()
+{
+	l n, k;
+	cin >> n >> k;
+	ordered_set<int> res;
+	for (l i = 1; i <= n; i++) {
+		res.insert(i);
+	}
+
+	auto last = res.begin();
+	int p = 0;
+	for (l i = 1; i <= n; i++) {
+		p = (p + k) % res.size();
+		last = res.find_by_order(p);
+		cout << *last << " ";
+		res.erase(last);
+	}
+	cout << "\n";
+}
+
+int main()
+{
+	ios::sync_with_stdio(0);
+	cin.tie(0);
+	solve();
+}