Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 150000 + 100;
  8.  
  9. map<char, queue<int>> cnt1, cnt2;
  10. int n;
  11. char l[N], r[N];
  12.  
  13. inline void read(){
  14. cin >> n;
  15. for(int i = 0; i < n; ++i){
  16. cin >> l[i];
  17. cnt1[l[i]].push(i);
  18. }
  19. for(int i = 0; i < n; ++i){
  20. cin >> r[i];
  21. cnt2[r[i]].push(i);
  22. }
  23. }
  24.  
  25. int main(void){
  26. read();
  27. vector<pair<int, int>> ans;
  28. for(char i = 'a'; i <= 'z'; ++i){
  29. if(!cnt1[i].empty() && !cnt2[i].empty()){
  30. while(!cnt1[i].empty() && !cnt2[i].empty()){
  31. int x = cnt1[i].front(), y = cnt2[i].front();
  32. cnt1[i].pop(), cnt2[i].pop();
  33. ans.push_back(make_pair(x + 1, y + 1));
  34. if(cnt2[i].empty() || cnt1[i].empty()){
  35. break;
  36. }
  37. }
  38. }
  39. }
  40. if(!cnt1['?'].empty()){
  41. for(char i = 'a'; i <= 'z'; ++i){
  42. if(!cnt1['?'].empty() && !cnt2[i].empty()){
  43. while(!cnt1['?'].empty() && !cnt2[i].empty()){
  44. int x = cnt1['?'].front(), y = cnt2[i].front();
  45. cnt1['?'].pop(), cnt2[i].pop();
  46. ans.push_back(make_pair(x + 1, y + 1));
  47. if(cnt2[i].empty() || cnt1['?'].empty()){
  48. break;
  49. }
  50. }
  51. }
  52. }
  53. }
  54. if(!cnt2['?'].empty()){
  55. for(char i = 'a'; i <= 'z'; ++i){
  56. if(!cnt2['?'].empty() && !cnt1[i].empty()){
  57. while(!cnt2['?'].empty() && !cnt1[i].empty()){
  58. int y = cnt2['?'].front(), x = cnt1[i].front();
  59. cnt2['?'].pop(), cnt1[i].pop();
  60. ans.push_back(make_pair(x + 1, y + 1));
  61. if(cnt1[i].empty() || cnt2['?'].empty()){
  62. break;
  63. }
  64. }
  65. }
  66. }
  67. }
  68. queue<int> q1 = cnt1['?'];
  69. queue<int> q2 = cnt2['?'];
  70. if(!q1.empty() && !q2.empty()){
  71. while(!q1.empty() && !q2.empty()){
  72. int x = q1.front(), y = q2.front();
  73. q1.pop(), q2.pop();
  74. ans.push_back(make_pair(x + 1, y + 1));
  75. if(q2.empty() || q1.empty()){
  76. break;
  77. }
  78. }
  79. }
  80. cout << ans.size() << endl;
  81. for(int i = 0; i < ans.size(); ++i){
  82. cout << ans[i].first << " " << ans[i].second << endl;
  83. }
  84. return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement