rotti321

galerie

May 16th, 2021
591
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <iostream>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. ifstream f("galerie.in");
  8. ofstream g("galerie.out");
  9.  
  10. int n,m,t,k,x,i,pas,inou,jnou,a[205][205],di[]={-1,0,1,0},dj[]={0,1,0,-1},sapa_cineva;
  11. struct cartita{int i,j,l,di,dj;}C[1000];
  12. set<int> s;
  13. set<int> sterse;
  14. set<int>::iterator it;
  15.  
  16. set<int>::iterator it1;
  17.  
  18. int interior(int i, int j)
  19. { if(i*j==0)return 0;
  20.   if(i>n)return 0;
  21.   if(j>m)return 0;
  22.   return 1;
  23. }
  24.  
  25. void uneste_galerii(int i,int j,int c1,int c2)
  26. { int k,i1,j1;
  27.     if(interior(i,j))
  28.      for(k=0;k<4;k++) {i1=i+di[k];j1=j+dj[k];
  29.                        if(a[i1][j1]==c1) { a[i1][j1]=c2;
  30.                                            uneste_galerii(i1,j1,c1,c2);
  31.                                           }
  32.                        }
  33. }
  34.  
  35. int main()
  36. { f>>k>>n>>m>>t;
  37.   for(i=1;i<=t;i++)
  38.   {f>>x;
  39.    if(x<=m) {C[i].i=0;C[i].j=x;C[i].di=1;C[i].dj=0;}
  40.      else
  41.      if(x<=n+m) {C[i].i=x-m;C[i].j=m+1; C[i].di=0;C[i].dj=-1;}
  42.      else
  43.      if(x<=2*m+n){C[i].i=n+1;C[i].j=2*m+n+1-x;C[i].di=-1;C[i].dj=0;}
  44.        else {C[i].i=2*n+2*m+1-x;C[i].j=0;C[i].di=0;C[i].dj=1;}
  45.     s.insert(i);
  46.   }
  47.   for(i=1;i<=n;i++)a[i][0]=a[i][m+1]=-1;
  48.   for(i=1;i<=m;i++)a[0][i]=a[n+1][i]=-1;
  49.  
  50.   while(!s.empty())
  51.   { sapa_cineva=0;
  52.     sterse.clear();
  53.     for(it=s.begin();it != s.end(); it++)
  54.       { i=*it;
  55.         inou=C[i].i+C[i].di;
  56.         jnou=C[i].j+C[i].dj;
  57.         x=a[inou][jnou];
  58.         if(x==0) {a[inou][jnou]=i;C[i].l++;C[i].i=inou;C[i].j=jnou;sapa_cineva=1;}
  59.         else
  60.          {   if(x!=-1)
  61.              {
  62.                uneste_galerii(inou,jnou,i,x);
  63.                C[x].l+=C[i].l;
  64.                if (x<i && a[inou+C[x].di][jnou+C[x].dj]!=x) sterse.insert(x);
  65.              }
  66.            sterse.insert(i);
  67.           }
  68.       }
  69.       for(it=sterse.begin();it != sterse.end(); it++)
  70.       { i=*it;
  71.         if(s.count(i)!=0) s.erase(i);
  72.       }
  73.  
  74.       if(sapa_cineva) pas++;
  75.   }
  76.   if(k==1) g<<pas<<'\n';
  77.      else
  78.      { x=C[1].l;
  79.        for(i=2;i<=t;i++) if(C[i].l>x)x=C[i].l;
  80.        g<<x<<'\n';
  81.      }
  82.  
  83.   f.close();g.close();
  84.     return 0;
  85. }
RAW Paste Data