fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <cmath>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include <iomanip>
  13. #include <deque>
  14. #include <chrono>
  15. #include <cassert>
  16. #include <bitset>
  17. #include <random>
  18.  
  19. using namespace std;
  20.  
  21. typedef int li;
  22. typedef  long double ld;
  23. const li MAX = 1e6 + 20;
  24.  
  25. li inf = (li)1e9;
  26. li mod = (li)1e9 + 7;
  27. li n, k, used[MAX];
  28. void solve() {
  29. 	cin >> n;
  30. 	for (int i = 0; i < n; i++) used[i] = 0;
  31. 	string ans = { 0 };
  32. 	used[0] = 1;
  33. 	used[n / 2] = 1;
  34. 	li curmod = n / 2;
  35. 	for (int i = 0; i < n - 1; i++) {
  36. 		if (curmod % 2) {
  37. 			ans.push_back(1);
  38. 			curmod--;
  39. 			if (used[(curmod + n) / 2]) {
  40. 				curmod = curmod / 2;
  41. 			}
  42. 			else {
  43. 				curmod = (curmod + n) / 2;
  44. 			}
  45. 		}
  46. 		else {
  47. 			ans.push_back(0);
  48. 			if (used[(curmod + n) / 2]) {
  49. 				curmod = curmod / 2;
  50. 			}
  51. 			else {
  52. 				curmod = (curmod + n) / 2;
  53. 			}
  54. 		}
  55. 		used[curmod] = 1;
  56. 	}
  57. 	reverse(ans.begin(), ans.end());
  58. 	for (int i = 0; i < n; i++) cout << int(ans[i]);
  59. 	cout << "\n";
  60.  }
  61. // 1 3 7 5
  62.  
  63. int main() {
  64. 	mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  65. 	ios::sync_with_stdio(0);
  66. 	freopen("unique.in", "r", stdin);
  67. 	li q;
  68. 	cin >> q;
  69. 	while (q--) solve();
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0s 4300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/6Tv9Fh
language:
C++14 (gcc 8.3)
created:
4 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!