Advertisement
Guest User

Untitled

a guest
Jun 27th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #pragma warning(disable:4786)
  2. #include<stdio.h>
  3. #include<set>
  4. #include<vector>
  5. using namespace std;
  6.  
  7. #define ABS(X) ((X)>0?(X):(-(X)))
  8.  
  9. int next[200002],prev[200002];
  10. int h[200002];
  11.  
  12. struct Pair
  13. {
  14. int a, b, hd;
  15. Pair(int x, int y)
  16. {
  17. a = x;
  18. b = y;
  19. hd = ABS(h[a]-h[b]);
  20. }
  21. };
  22.  
  23. bool operator<(Pair A, Pair B)
  24. {
  25. if( A.hd < B.hd ) return 1;
  26. if( A.hd > B.hd ) return 0;
  27.  
  28. if(A.a < B.a) return 1;
  29. return 0;
  30. }
  31.  
  32. char word[200003];
  33. set<Pair> S;
  34. vector<Pair> V;
  35. int done[200003];
  36.  
  37. int main()
  38. {
  39. int n,i;
  40. Pair Y(0,0);
  41. set<Pair>::iterator X;
  42.  
  43. scanf("%d%s",&n,word);
  44. for(i=0;i<n;i++)
  45. {
  46. scanf("%d",&h[i]);
  47. prev[i] = i-1;
  48. next[i] = i+1;
  49. done[i]=0;
  50. }
  51.  
  52. for(i=0;i<n-1;i++)
  53. {
  54. if(word[i]!=word[i+1])
  55. S.insert( Pair(i,i+1) );
  56. }
  57.  
  58. while(!S.empty())
  59. {
  60. X = S.begin();
  61. Y = Pair(X->a, X->b);
  62. S.erase(X);
  63. if(done[Y.a] || done[Y.b]) continue;
  64. done[Y.a]=1; done[Y.b]=1;
  65. V.push_back( Y );
  66. if(prev[Y.a]!=-1) next[ prev[Y.a] ] = next[ Y.b ];
  67. if(next[Y.b]!=n) prev[ next[Y.b] ] = prev[ Y.a ];
  68. if(prev[Y.a]!=-1 && next[Y.b]!=n && word[prev[Y.a]]!=word[next[Y.b]])
  69. S.insert( Pair(prev[Y.a],next[Y.b]) );
  70. }
  71.  
  72. printf("%d\n",V.size());
  73. for(i=0;i<V.size();i++)
  74. printf("%d %d\n",V[i].a+1,V[i].b+1 );
  75. return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement