fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/rope>
  3.  
  4. using namespace std;
  5. using namespace __gnu_cxx;
  6.  
  7. rope<int> forv, rev, one, two, init;
  8. string s;
  9.  
  10. void fail()
  11. {
  12. 	cout << "Bad Luck Allen\n";
  13. 	exit(0);
  14. }
  15.  
  16. const int maxn = 1e5 + 7, sigma = 26;
  17.  
  18. int p[maxn];
  19. int assigned[maxn];
  20.  
  21. int get(int v)
  22. {
  23. 	if(p[v] == v) return v;
  24. 	return p[v] = get(p[v]);
  25. }
  26.  
  27. void uni(int a, int b)
  28. {
  29. 	a = get(-a);
  30. 	b = get(-b);
  31. 	if(assigned[a] && assigned[b])
  32. 		if(assigned[a] != assigned[b])
  33. 			fail();
  34. 	if(assigned[a])
  35. 		assigned[b] = assigned[a];
  36. 	p[a] = b;
  37. }
  38.  
  39. void assig(int a, int b)
  40. {
  41. 	a = get(-a);
  42. 	if(assigned[a] && assigned[a] != b)
  43. 		fail();
  44. 	assigned[a] = b;
  45. }
  46.  
  47. int main()
  48. {
  49. 	//freopen("input.txt", "r", stdin);
  50.     ios::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     iota(p, p + maxn, 0);
  53.     int64_t n, m, k;
  54.     cin >> n >> m >> k;
  55.     cin >> s;
  56.     int cnt = 0;
  57.     for(int i = 0; i < n; i++)
  58. 		if(s[i] == '?')
  59. 			forv.push_back(--cnt);
  60. 		else
  61. 			forv.push_back(s[i]);
  62.  
  63.     for(int i = n - 1; i >= 0; i--)
  64. 		if(s[i] == '?')
  65. 			rev.push_back(cnt++);
  66. 		else
  67. 			rev.push_back(s[i]);
  68.     init = forv;
  69. 	while(m--)
  70. 	{
  71. 		int l, r;
  72. 		cin >> l >> r;
  73. 		l--, r--;
  74.  
  75.         one = forv.substr(l, r - l + 1);
  76.         two = rev.substr(n - r - 1, r - l + 1);
  77.  
  78.         forv.erase(l, r - l + 1);
  79.         rev.erase(n - r - 1, r - l + 1);
  80.  
  81.         forv.insert(l, two);
  82.         rev.insert(n - r - 1, one);
  83. 	}
  84.     for(int i = 0; i < n; i++)
  85. 		if(init[i] != forv[i])
  86. 		{
  87. 			if(init[i] > 0 && forv[i] > 0)
  88. 				fail();
  89. 			if(init[i] < 0 && forv[i] < 0)
  90. 				uni(init[i], forv[i]);
  91. 			if(init[i] > 0)
  92. 				assig(forv[i], init[i]);
  93. 			if(forv[i] > 0)
  94. 				assig(init[i], forv[i]);
  95. 		}
  96. 	vector<int> represent;
  97.     k--;
  98. 	while(k)
  99. 	{
  100. 		represent.push_back(k % sigma);
  101. 		k /= sigma;
  102. 	}
  103. 	for(int i = 0; i < n; i++)
  104. 		if(init[i] < 0 && !assigned[get(-init[i])] && get(-init[i]) == -init[i])
  105. 			cnt++;
  106.     if(represent.size() > cnt)
  107.         fail();
  108.     string ans;
  109.     for(int i = 0; i < n; i++)
  110.     {
  111.         if(init[i] > 0)
  112. 			ans.push_back(char(init[i]));
  113. 		else if(assigned[get(-init[i])])
  114. 			ans.push_back(assigned[get(-init[i])]);
  115. 		else if(cnt > represent.size())
  116. 		{
  117. 			assig(init[i], 'a');
  118. 			ans.push_back('a');
  119. 			cnt--;
  120. 		}
  121. 		else
  122. 		{
  123. 			assig(init[i], 'a' + represent[cnt - 1]);
  124. 			ans.push_back('a' + represent[cnt - 1]);
  125. 			cnt--;
  126. 		}
  127.     }
  128.     cout << ans << "\n";
  129.     return 0;
  130. }
  131.  
Runtime error #stdin #stdout 0.14s 13376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oQF6U0
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!