Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. bool soman( map<int,int>m , vector<int> v , int s , int e )
  5. {
  6.  
  7. bool flag = true ;
  8.  
  9. for( int i = s ; i <= e ; i++ ) {
  10.  
  11. if( m[v[i]] != m[-v[i]] ) {
  12.  
  13. return false ;
  14.  
  15. }
  16.  
  17. }
  18.  
  19. return true ;
  20.  
  21. }
  22.  
  23. map<int,int> gona( vector<int> v , int s , int e )
  24. {
  25.  
  26. map<int,int> m ;
  27.  
  28. for( int i = s ; i <= e ; i++ ) m[v[i]]++ ;
  29.  
  30. return m ;
  31.  
  32. }
  33.  
  34. pair<int,int> func( vector<int> v , int s , int e )
  35. {
  36. // cout << s << " " << e << endl ;
  37.  
  38. pair<int,int> zero = { 0 , 0 } ;
  39.  
  40. map<int,int> m ;
  41.  
  42. for( int i = e ; i < v.size() ; i++ ) {
  43.  
  44. m = gona( v , s , i ) ;
  45.  
  46. if( false == soman( m , v , s , i ) ) {
  47.  
  48. continue ;
  49.  
  50. }
  51.  
  52. else {
  53.  
  54. pair<int,int> ei_je = { s , i } ;
  55.  
  56. for( auto x = m.begin() ; x != m.end() ; x++ ) {
  57.  
  58. int val = x->second ;
  59.  
  60. if( val >= 2 ) return zero ;
  61.  
  62. }
  63. // cout << s << " " << i << endl ;
  64. return ei_je ;
  65.  
  66. }
  67.  
  68. }
  69.  
  70.  
  71.  
  72. // return zero ;
  73.  
  74. }
  75.  
  76. int main( void )
  77. {
  78.  
  79. int n ;
  80.  
  81. cin >> n ;
  82.  
  83. vector<int> v( n ) ;
  84.  
  85. map<int,int> m ;
  86.  
  87. bool flag = true ;
  88.  
  89. for( int i = 0 ; i < n ; i++ ) {
  90.  
  91. cin >> v[i] ;
  92.  
  93. m[v[i]]++ ;
  94.  
  95. if( v[i] < 0 ) {
  96.  
  97. int pos_freq = m[-v[i]] , neg_freq = m[v[i]] ;
  98.  
  99. if( neg_freq > pos_freq ) {
  100.  
  101. flag = false ;
  102.  
  103. }
  104.  
  105. }
  106.  
  107. else if( v[i] > 0 ) {
  108.  
  109. int pp = m[v[i]] , nn = m[-v[i]] ;
  110.  
  111. int dif = pp-nn ;
  112.  
  113. if( dif >= 2 ) {
  114.  
  115. flag = false ;
  116.  
  117. }
  118.  
  119. }
  120.  
  121. }
  122.  
  123. for( int i = 0 ; i < n ; i++ ) {
  124.  
  125. if( m[v[i]] != m[-v[i]] ) {
  126.  
  127. flag = false ;
  128.  
  129. }
  130.  
  131. }
  132.  
  133. if( flag == false ) {
  134.  
  135. cout << -1 << endl ;
  136.  
  137. }
  138.  
  139. else {
  140.  
  141. vector<pair<int,int>> vpp ;
  142.  
  143. pair<int,int> qq = { 0 , 0 } ;
  144.  
  145. for( int i = 0 ; i < n ; i++ ) {
  146.  
  147. int val = v[i] , oppo = -v[i] ;
  148.  
  149.  
  150.  
  151. for( int j = i+1 ; j < n && val > 0 ; j++ ) {
  152.  
  153. if( v[j] == oppo ) {
  154.  
  155. pair<int,int> pp = func( v , i , j ) ;
  156.  
  157. // cout << pp.first << " xie " << pp.second << endl ;
  158.  
  159. // cout << "i : " << i << " j : " << j << endl ;
  160.  
  161. // cout << vpp.size() << endl ;
  162.  
  163. if( pp == qq ) {
  164.  
  165. // cout << "soman\n" ;
  166.  
  167. flag = false ;
  168.  
  169. break ;
  170.  
  171. }
  172.  
  173. else {
  174.  
  175. vpp.emplace_back( pp.first , pp.second ) ;
  176.  
  177. i = pp.second ;
  178.  
  179. break ;
  180.  
  181. // cout << pp.first << " " << pp.second << endl ;
  182.  
  183. }
  184.  
  185.  
  186. }
  187.  
  188. }
  189.  
  190. }
  191.  
  192. if( flag == false ) {
  193.  
  194. cout << -1 << endl ; // cout << "ya123\n" ;
  195.  
  196. }
  197.  
  198. else {
  199.  
  200. cout << vpp.size() << endl ; // cout << "yes\n" ;
  201.  
  202. for( int i = 0 ; i < vpp.size() ; i++ ) {
  203.  
  204. // cout << vpp[i].first << " " << vpp[i].second << endl ;
  205.  
  206. cout << abs( vpp[i].first - vpp[i].second ) + 1 << " " ;
  207.  
  208. }
  209.  
  210. }
  211.  
  212. }
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224. return 0 ;
  225.  
  226. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement