2019-06-23から1日間の記事一覧

Codeforces Round #567 (Div. 2) E2. A Story of One Country (Hard)

https://codeforces.com/contest/1181/problem/E2The solution is based on the following fact: T(n) = T(x) + T(n - x) + min(x, n - x) = O(n log n)Analysis: Looking at one specific element, when the element moves to the smaller group, it takes …

SRM 761 500pts. SortArray

From 0-1 sorting lemma, we have an algorithm. #include <bits/stdc++.h> using namespace std; struct SortArray { vector<int> verify(int N, vector<int> commands) { for (int i = 0; i < 1 << N; i++) { vector<int> a(N); for (int j = 0; j < N; j++) { a[j] = i >> j & 1; } for </int></int></int></bits/stdc++.h>…