fork download
copy 
  1. /**
  2.  * code generated by JHelper
  3.  * More info: https://g...content-available-to-author-only...b.com/AlexeyDmitriev/JHelper
  4.  * @author RiaD
  5.  */
  6.  
  7. #include <iostream>
  8. #include <fstream>
  9.  
  10. #include <iostream>
  11. #include <cassert>
  12. #include <vector>
  13. #include <algorithm>
  14.  
  15.  
  16. #include <iterator>
  17.  
  18.  
  19. #include <string>
  20. #include <stdexcept>
  21.  
  22. #ifndef SPCPPL_ASSERT
  23. 	#ifdef SPCPPL_DEBUG
  24. 		#define SPCPPL_ASSERT(condition) \
  25. 		if(!(condition)) { \
  26. 			throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
  27. 		}
  28. 	#else
  29. 		#define SPCPPL_ASSERT(condition)
  30. 	#endif
  31. #endif
  32.  
  33.  
  34. /**
  35. * Support decrementing and multi-passing, but not declared bidirectional(or even forward) because
  36. * it's reference type is not a reference.
  37. *
  38. * It doesn't return reference because
  39. * 1. Anyway it'll not satisfy requirement [forward.iterators]/6
  40. *   If a and b are both dereferenceable, then a == b if and only if *a and
  41. *   b are bound to the same object.
  42. * 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator
  43. *
  44. * Note, reverse_iterator is not guaranteed to work  now too since it works only with bidirectional iterators,
  45. * but it's seems to work at least on my implementation.
  46. *
  47. * It's not really useful anywhere except iterating anyway.
  48. */
  49. template <typename T>
  50. class IntegerIterator {
  51. public:
  52. 	using value_type = T;
  53. 	using difference_type = std::ptrdiff_t;
  54. 	using pointer = T*;
  55. 	using reference = T;
  56. 	using iterator_category = std::input_iterator_tag;
  57.  
  58. 	explicit IntegerIterator(T value): value(value) {
  59.  
  60. 	}
  61.  
  62. 	IntegerIterator& operator++() {
  63. 		++value;
  64. 		return *this;
  65. 	}
  66.  
  67. 	IntegerIterator operator++(int) {
  68. 		IntegerIterator copy = *this;
  69. 		++value;
  70. 		return copy;
  71. 	}
  72.  
  73. 	IntegerIterator& operator--() {
  74. 		--value;
  75. 		return *this;
  76. 	}
  77.  
  78. 	IntegerIterator operator--(int) {
  79. 		IntegerIterator copy = *this;
  80. 		--value;
  81. 		return copy;
  82. 	}
  83.  
  84. 	T operator*() const {
  85. 		return value;
  86. 	}
  87.  
  88. 	bool operator==(IntegerIterator rhs) const {
  89. 		return value == rhs.value;
  90. 	}
  91.  
  92. 	bool operator!=(IntegerIterator rhs) const {
  93. 		return !(*this == rhs);
  94. 	}
  95.  
  96. private:
  97. 	T value;
  98. };
  99.  
  100. template <typename T>
  101. class IntegerRange {
  102. public:
  103. 	IntegerRange(T begin, T end): begin_(begin), end_(end) {
  104. 		SPCPPL_ASSERT(begin <= end);
  105. 	}
  106.  
  107. 	IntegerIterator<T> begin() const {
  108. 		return IntegerIterator<T>(begin_);
  109. 	}
  110.  
  111. 	IntegerIterator<T> end() const {
  112. 		return IntegerIterator<T>(end_);
  113. 	}
  114.  
  115. private:
  116. 	T begin_;
  117. 	T end_;
  118. };
  119.  
  120. template <typename T>
  121. class ReversedIntegerRange {
  122. 	using IteratorType = std::reverse_iterator<IntegerIterator<T>>;
  123. public:
  124. 	ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) {
  125. 		SPCPPL_ASSERT(begin >= end);
  126. 	}
  127.  
  128. 	IteratorType begin() const {
  129. 		return IteratorType(IntegerIterator<T>(begin_));
  130. 	}
  131.  
  132. 	IteratorType end() const {
  133. 		return IteratorType(IntegerIterator<T>(end_));
  134. 	}
  135.  
  136. private:
  137. 	T begin_;
  138. 	T end_;
  139. };
  140.  
  141. template <typename T>
  142. IntegerRange<T> range(T to) {
  143. 	return IntegerRange<T>(0, to);
  144. }
  145.  
  146. template <typename T>
  147. IntegerRange<T> range(T from, T to) {
  148. 	return IntegerRange<T>(from, to);
  149. }
  150.  
  151. template <typename T>
  152. IntegerRange<T> inclusiveRange(T to) {
  153. 	return IntegerRange<T>(0, to + 1);
  154. }
  155.  
  156. template <typename T>
  157. IntegerRange<T> inclusiveRange(T from, T to) {
  158. 	return IntegerRange<T>(from, to + 1);
  159. }
  160.  
  161. template <typename T>
  162. ReversedIntegerRange<T> downrange(T from) {
  163. 	return ReversedIntegerRange<T>(from, 0);
  164. }
  165.  
  166. template <typename T>
  167. ReversedIntegerRange<T> downrange(T from, T to) {
  168. 	return ReversedIntegerRange<T>(from, to);
  169. }
  170.  
  171. template <typename T>
  172. ReversedIntegerRange<T> inclusiveDownrange(T from) {
  173. 	return ReversedIntegerRange<T>(from + 1, 0);
  174. }
  175.  
  176. template <typename T>
  177. ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  178. 	return ReversedIntegerRange<T>(from + 1, to);
  179. }
  180.  
  181. //#define PROBLEM "problem_name.h"
  182. //#include PROBLEM
  183. //#include <message.h>
  184. //#include <spcppl/dgcj.h>
  185.  
  186. using namespace std;
  187.  
  188. class E3SortirovkaSliyaniem {
  189. public:
  190. 	static constexpr int kStressCount = 0;
  191.  
  192. 	static void generateTest(std::ostream& test) {
  193. 	}
  194.  
  195. 	void solve(std::istream& in, std::ostream& out) {
  196. 		//static int testnumber = 0;
  197. 		//out << "Case #" << ++testnumber << ": ";
  198. 		//cerr << "test " << testnumber << endl;
  199.  
  200. 		string s;
  201. 		in >> s;
  202. 		int ptr = 0;
  203.  
  204. 		auto go = [&](auto& go, int l, int r) {
  205. 			if (r - l <= 1) {
  206. 				return;
  207. 			}
  208. 			int m = (l + r) >> 1;
  209. 			go(go, l, m);
  210. 			go(go, m, r);
  211. 			int cnt0 = 0;
  212. 			int cnt1 = 0;
  213. 			while (cnt0 < m - l && cnt1 < r - m) {
  214. 				if (ptr == s.size()) {
  215. 					throw 1;
  216. 				}
  217. 				if (s[ptr++] == '0') {
  218. 					++cnt0;
  219. 				}
  220. 				else {
  221. 					++cnt1;
  222. 				}
  223. 			}
  224. 		};
  225.  
  226. 		vector<int> a;
  227. 		vector<int> b;
  228. 		auto res = [&](auto& go, int l, int r) {
  229. 			if (r - l <= 1) {
  230. 				return;
  231. 			}
  232. 			int m = (l + r) >> 1;
  233. 			go(go, l, m);
  234. 			go(go, m, r);
  235. 			int i = l;
  236. 			int j = m;
  237. 			int k = l;
  238. 			while (i < m and j < r) {
  239. 				assert(ptr != s.size());
  240. 				if (s[ptr++] == '0') {
  241. 					b[k++] = a[i++];
  242. 				}
  243. 				else {
  244. 					b[k++] = a[j++];
  245. 				}
  246. 			}
  247. 			while (i < m) {
  248. 				b[k++] = a[i++];
  249. 			}
  250. 			while (j < r) {
  251. 				b[k++] = a[j++];
  252. 			}
  253.  
  254. 			for (int i: range(l, r)) {
  255. 				a[i] = b[i];
  256. 			}
  257. 		};
  258.  
  259. 		int l = 1, r = 100000;
  260. 		while (l <= r) {
  261. 			int m = (l + r) / 2;
  262.  
  263. 			try {
  264. 				ptr = 0;
  265. 				go(go, 0, m);
  266. 			}
  267. 			catch (int) {
  268. 				r = m - 1;
  269. 				continue;
  270. 			}
  271. 			if (ptr == s.size()) {
  272. 				int i = m;
  273. 				out << i << "\n";
  274. 				a.resize(i);
  275. 				b.resize(i);
  276. 				for (int j: range(i)) {
  277. 					a[j] = j;
  278. 				}
  279. 				ptr = 0;
  280. 				res(res, 0, i);
  281. 				vector<int> c(a.size());
  282. 				for (int t: range(a.size())) {
  283. 					b[a[t]] = t;
  284. 				}
  285. 				for (int x: b) {
  286. 					out << x + 1 << " ";
  287. 				}
  288. 				return;
  289. 			}
  290. 			l = m + 1;
  291. 		}
  292.  
  293. 	}
  294. };
  295.  
  296.  
  297. int main() {
  298. 	std::ios_base::sync_with_stdio(false);
  299. 	E3SortirovkaSliyaniem solver;
  300. 	std::istream& in(std::cin);
  301. 	std::ostream& out(std::cout);
  302. 	in.tie(nullptr);
  303. 	out << std::fixed;
  304. 	out.precision(20);
  305. 	solver.solve(in, out);
  306. 	return 0;
  307. }
Success #stdin #stdout 0.01s 5372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1
https://ideone.com/2pV7jB
language:
C++14 (gcc 8.3)
created:
3 years 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!