Advertisement
Kevin_Zhang

Untitled

Feb 20th, 2021
887
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. /*************************************************************************
  2.  *                                                                       *
  3.  *                     XVI Olimpiada Informatyczna                       *
  4.  *                                                                       *
  5.  *   Zadanie:  Kodowanie (KOD)                                           *
  6.  *   Plik:     kod.cpp                                                   *
  7.  *   Autor:    Piotr Niedzwiedz                                          *
  8.  *   Opis:     Rozwiazanie wzorcowe O(L)                                 *
  9.  *                                                                       *
  10.  *************************************************************************/
  11.  
  12. #include<cstdio>
  13. #include<cstdlib>
  14. #include<cstring>
  15. #include<algorithm>
  16. using namespace std;
  17.  
  18. #define FOR(I,A,B) for(int I=(A);I<=(B);++I)
  19. #define FORD(I,A,B) for(int I=(A);I>=(B);--I)
  20. #define REP(I,N) for(int I=0;I<(N);++I)
  21.  
  22. const int nmx=1500000;
  23. int n,l,wh;
  24. int S[2][nmx],L[nmx],W[nmx];
  25. bool wazny[nmx],synch[nmx];
  26. bool byl[nmx];
  27.  
  28. void dfs1(int x,int y){
  29.     if (!S[0][y]){
  30.         if(!wazny[x]){
  31.             wazny[x]=1;
  32.             W[wh++]=x;
  33.         }
  34.     }
  35.     else if (S[0][x]) {
  36.         dfs1(S[0][x],S[0][y]);
  37.         dfs1(S[1][x],S[1][y]);
  38.     }
  39. }
  40.  
  41. void dfs2(int x,int y){
  42.     if (!S[0][y]){
  43.         if(!wazny[x]){
  44.             wazny[x]=1;
  45.             W[wh++]=x;
  46.         }
  47.     }
  48.     else{
  49.         if (!S[0][x]){
  50.             if (!byl[y]){
  51.                 byl[y]=1;
  52.                 dfs2(0,y);
  53.             }
  54.         }
  55.         else{
  56.             dfs2(S[0][x],S[0][y]);
  57.             dfs2(S[1][x],S[1][y]);
  58.         }
  59.     }
  60. }
  61.  
  62. void dfs3(int x,int y){
  63.     if (!S[0][y]){
  64.         if(S[0][x]) synch[y]=0;
  65.     }
  66.     else{
  67.         if (!S[0][x]){
  68.             if (!byl[y]){
  69.                 byl[y]=1;
  70.                 dfs3(0,y);
  71.             }
  72.         }
  73.         else{
  74.             dfs3(S[0][x],S[0][y]);
  75.             dfs3(S[1][x],S[1][y]);
  76.         }
  77.     }
  78. }
  79.  
  80.  
  81.  
  82. int main()
  83. {
  84.     static char buf[3000002];
  85.     static int stos[nmx];
  86.     int m,h=1,z;
  87.     n=1;
  88.     scanf("%d%s",&m,buf);
  89.     REP(i,m)    switch(buf[i]){
  90.         case 'B':
  91.             h--;
  92.             break;
  93.         case 'X':
  94.             L[l++]=stos[h-1];
  95.             break;
  96.         default:
  97.             z=buf[i]-'0';
  98.             S[z][stos[h-1]]=n;
  99.             stos[h++]=n++;
  100.             break; 
  101.     }
  102.     REP(i,n) dfs1(0,i);
  103.     for(int i=0;i<wh;++i) dfs2(W[i],0);
  104.     REP(i,n) byl[i]=0;
  105.     REP(i,l) synch[L[i]]=1;
  106.     REP(i,wh) dfs3(W[i],0);
  107.     int wynik=0;
  108.     REP(i,l) if(synch[L[i]]) wynik++;
  109.     printf("%d\n",wynik);
  110.     REP(i,l) if(synch[L[i]]) printf("%d\n",i+1);
  111.     return 0;
  112. }  
  113.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement