competitive-coding/codechef/MAY17WSITES013.cpp at master · ravibitsgoa/competitive-coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<string>
#include<iostream>
#include<boost/container/flat_map.hpp>
#define endl '\n'     //Obvious: to avoid flushes.
using namespace std;
int main()
{ long unsigned int n;
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin>>n;
  boost::container::flat_map<string, char> sites;
  char x; string name;
  for(int i=0; i<n; i++)
  { cin>>x>>name;
    sites[name]=x;
  }
  boost::container::flat_map<string, char> :: iterator i;
  int filter=0;
  string filters[n];
  for(i=sites.begin(); i!=sites.end(); i++)
  { if(i->second == '+')//Is any legit website blocked by a previous filter? (test case # 13 & 14 will pass due to this.)
    { for(int k=0; k<filter; k++)
      { if(filters[k][0]!=(i->first)[0]) //There's no point in comparing the filter and the website if the first char don't match.
          continue;
        size_t found = (i->first).find(filters[k]);
        if(found==0) //This means the filter is found at starting of ith string.
        { cout<<-1; return 0;
        }
      }
    }

    else
    {
      //Let's check if current website is already blocked or not.
      bool blockedornot=0;
      for(int k=0; k<filter; k++)
      { if(filters[k][0]!=(i->first)[0]) //There's no point in comparing the filter and the website if the first char don't match.
          continue;
        size_t found = (i->first).find(filters[k]);
        if(found==0) //This means the filter is found at starting of ith string.
        { blockedornot=1;
          break;
        }
      }
      if(blockedornot==1)//Do nothing if current website is already blocked.
        continue;

      int temp=filter;
      for(boost::container::flat_map<string, char> :: reverse_iterator j(i); j!=sites.rend(); j++)
      { if(j->second=='+')  //To find the first allowed website just before the current one.
        { int k=0;
          char newfilter[(i->first).length()];
          while((k<(i->first).length()) && (k<(j->first).length()) && ((i->first)[k]==(j->first)[k])) //To add all the same characters to the filter.
          { newfilter[k]=(i->first)[k];
            k++;
          }

          if(k==(i->first).length())//This means ith website is subset of jth website. So designing a filter is impossible task...
          { cout<<-1;
            return 0;
          }
          newfilter[k]=(i->first)[k]; //To add the first differing character.
          newfilter[k+1]='\0'; //To remove the garbage characters.
          filters[filter++]=newfilter;
          //cout<<newfilter<<endl;
          break;
        }
      }
      //This finds the lexographically previous allowed (+) website, before the current one.
      //Then, compares it char by char with the current website, makes a filter, and adds it into the list of filters.

      for(boost::container::flat_map<string, char> :: iterator j=i; j!=sites.end(); j++)
      { if(j->second=='+')
        { int k=0;
          char newfilter[(i->first).length()];
          while(k<(i->first).length() && (k<(j->first).length()) && (i->first)[k]==(j->first)[k])
          { newfilter[k]=(i->first)[k];
            k++;
          }
          if(k==(i->first).length())
          { cout<<-1;
            return 0;
          }
          newfilter[k]=(i->first)[k];
          newfilter[k+1]='\0';
          if(filter>0 && k>=filters[filter-1].length() && 0 == (i->first).find(filters[filter-1]))//If this overlaps with the last filter.
          { filters[filter-1]=newfilter;
          }//e.g. last filter -> "codec" & current one is "codechef".
          else if(filter==0 || 0 != (i->first).find(filters[filter-1]))
          { filters[filter++]=newfilter;
	    //cout<<'a'<<i->first<<endl;
          }//If this is the first ever filter to be stored or this is the first filter of ith (THIS) website.

          //cout<<newfilter<<endl;
          break;
        }
      }// This just finds the lexographically next allowed (+) website after the current blocked website.
      //Then, compares it char by char with the current website, makes a filter, which replaces the previous filter if be long enough.

      if(temp==filter && filter>0 && filters[filter-1][0]!=(i->first)[0])
      { char newfilter=(i->first) [0];
        filters[filter++]=newfilter;
	//cout<<'0';
      }
      else if(temp==filter && filter==0)
      { char newfilter=(i->first) [0];
        filters[filter++]=newfilter;
	//cout<<'0';
      }
    }
  }
  cout<<filter<<endl;         //Print the number of filters.
  for(int i=0; i<filter; i++)
    cout<<filters[i]<<endl;   //And, the filters.
}