Submission #138855

#	Time	Username	Problem	Language	Result	Execution time	Memory
138855		mihnea_anghel	Lozinke (COCI17_lozinke)	C++17	100 / 100	266 ms	2392 KiB

lozinke

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>
//#define cin in
//#define cout out

using namespace std;
//ifstream in ( "COCI17_LOZINKE.in" );
//ofstream out( "COCI17_LOZINKE.out" );

int sol, n, i, j, k;
string s[20010], sc;
set < string > st;
map < string, int > m;
set < string >:: iterator it;

bool cmp ( string a, string b ){
    if ( a.size() != b.size() ) return a.size() < b.size();
    return a<b;
}

int main() {
    cin >> n;
    for ( i=1; i <= n; i++ ) cin>> s[i]; //pe fiecare parola o citesc intr un string ca pe un intreg
    sort ( s+1, s+n+1, cmp ); //sortez alfabetic
    for ( i=1; i <= n; i++ ){
        st.clear(); //practic setul asta cuprinde toate subcuvintele parolei si acum il sterg pe cel de la parola anterioara
        for ( j=0; j < s[i].size(); j++ ){
            sc.erase( sc.begin(), sc.end() ); // stringul asta contine la fiecare pas un nou subcuvant
            for ( k=j; k <s[i].size(); k++ ){
                sc.push_back(s[i][k]); // adaug litera noua
                st.insert(sc); //adaug subcuvantul nou in set !! se pune doar daca n a mai fost gasit ca e set, nu multiset..
            }
        }
        for ( it = st.begin(); it != st.end(); it++ ) //parcurg setul cu subcuvintele parolei curente
            if ( m.find(*it) != m.end() ) // daca exista o parola in map identica cu subcuvantul curent
                sol += m[*it]; // adaug numarul de dati in care apare
        
        if ( m.find(s[i]) != m.end() ) // daca mai exista parola
            m[s[i]]++; //cresc nr de ori de care apare
        else m[s[i]] = 1;
    }
    
    int nr = 1;
    for ( i=2; i <= n; i++){
        if ( s[i] == s[i-1] )
            nr++;
        else nr=1;
        sol += nr-1;
    }
    cout<<sol;
    return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( j=0; j < s[i].size(); j++ ){
                    ~~^~~~~~~~~~~~~
lozinke.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for ( k=j; k <s[i].size(); k++ ){
                        ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100