fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXV = 6.1e5;
  5. const int MAXN = 13;
  6. int p3[MAXN];
  7. int n;
  8.  
  9. struct node {
  10. 	union {
  11. 		int idx;
  12. 		node* c[3];
  13. 	};
  14. 	bool lazy;
  15. };
  16. node node_pool[MAXV * 3];
  17. int node_idx = 0;
  18.  
  19. node* init(int cur, int pos) {
  20. 	node* v = &(node_pool[node_idx++]);
  21. 	if (cur == n) {
  22. 		// leaf
  23. 		v->idx = pos;
  24. 	} else {
  25. 		for (int x = 0; x < 3; x++) {
  26. 			v->c[x] = init(cur+1, pos + p3[cur] * x);
  27. 		}
  28. 	}
  29. 	return v;
  30. }
  31.  
  32. void apply(node* v) {
  33. 	assert(v);
  34. 	v->lazy = !v->lazy;
  35. 	swap(v->c[1], v->c[2]);
  36. }
  37.  
  38. void propagate(node* v) {
  39. 	if (!v->lazy) return;
  40. 	v->lazy = false;
  41. 	for (int x = 0; x < 3; x++) apply(v->c[x]);
  42. }
  43.  
  44. void upd(node* v, int cur) {
  45. 	if (cur == n) {
  46. 		// leaf
  47. 	} else {
  48. 		propagate(v);
  49. 		swap(v->c[1], v->c[2]);
  50. 		swap(v->c[0], v->c[1]);
  51. 		upd(v->c[0], cur+1);
  52. 	}
  53. }
  54.  
  55. int ans[MAXV];
  56.  
  57. void dfs(node* v, int cur, int pos) {
  58. 	if (cur == n) {
  59. 		ans[v->idx] = pos;
  60. 	} else {
  61. 		propagate(v);
  62. 		for (int x = 0; x < 3; x++) dfs(v->c[x], cur+1, pos + x * p3[cur]);
  63. 	}
  64. }
  65.  
  66. int main() {
  67. 	ios::sync_with_stdio(0), cin.tie(0);
  68. 	string t;
  69. 	cin >> n >> t;
  70. 	p3[0] = 1;
  71. 	for (int i = 1; i <= n; i++) p3[i] = p3[i-1] * 3;
  72. 	node* tr = init(0, 0);
  73. 	for (char op : t) {
  74. 		if (op == 'R') {
  75. 			upd(tr, 0);
  76. 		} else if (op == 'S') {
  77. 			apply(tr);
  78. 		} else assert(false);
  79. 	}
  80. 	dfs(tr, 0, 0);
  81. 	for (int i = 0; i < p3[n]; i++) {
  82. 		cout << ans[i] << " \n"[i+1==p3[n]];
  83. 	}
  84. }
  85.  
Success #stdin #stdout 0s 4364KB
comments (?)
stdin 
3
SRSRRSRRRSRRRR
stdout 
23 9 22 8 3 7 20 24 19 5 18 4 17 12 16 2 6 1 14 0 13 26 21 25 11 15 10
https://ideone.com/138FQP
language:
C++14 (gcc 8.3)
created:
5 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!