Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// Virus Polimorfo, Alen Antonelli, 23/09/17 http://www.oia.unsam.edu.ar/_media/prob/c3a10n3p2.pdf
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Datos {
- vector <int> cadena;
- int n, m;
- void leer ()
- {
- cin>>n>>m;
- cadena.resize(n+1);
- cadena[0] = 0; ///para que funcione la lógica mas tarde
- for (int i=1; i<=n; i++)
- cin>>cadena[i];
- }
- void antivirus ()
- {
- vector <int> anti(n+1), pos;
- int cant = 0;
- if ( n>=m )
- {
- for (int i= 1; i<m; i++) ///precarga los primeros m-1 datos
- {
- int caracter = cadena[i];
- if (1<=caracter && caracter<=m)
- {
- if(!anti[caracter])
- cant++;
- anti[ caracter ]++;
- }
- }
- for (int i=m; i<=n; i++) /// procesa en base a la bolsita (anti)
- {
- int pos_ant = i-m;
- int pos_sig = i;
- int caract_ant = cadena[pos_ant];
- int caract_sig = cadena[pos_sig];
- if ( (1<=caract_ant) && (caract_ant<=m) )
- {
- anti[caract_ant]--;
- if (!anti[caract_ant])
- cant--;
- }
- if ( (1<=caract_sig) && (caract_sig<=m) )
- {
- if (!anti[caract_sig])
- cant++;
- anti[caract_sig]++;
- }
- if (cant==m)
- pos.push_back(pos_ant+1);///el siguiente a la pos anterior
- }
- }
- cout<<endl<<pos.size()<<endl;
- for (int i=0; i<pos.size(); i++)
- cout<<pos[i]<<" ";
- }
- };
- int main ()
- {
- Datos d;
- d.leer();
- d.antivirus();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment