oj.uz

Submission #138855

# Submission time Handle Problem Language Result Execution time Memory
138855 2019-07-30T14:29:44 Z mihnea_anghel Lozinke (COCI17_lozinke) C++17
100 / 100
 266 ms 2392 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 11 ms 1016 KB Output is correct
6 Correct 19 ms 1016 KB Output is correct
7 Correct 22 ms 1116 KB Output is correct
8 Correct 25 ms 1144 KB Output is correct
9 Correct 94 ms 1528 KB Output is correct
10 Correct 127 ms 1596 KB Output is correct
11 Correct 151 ms 1740 KB Output is correct
12 Correct 240 ms 1912 KB Output is correct
13 Correct 242 ms 2180 KB Output is correct
14 Correct 230 ms 2392 KB Output is correct
15 Correct 266 ms 2168 KB Output is correct
16 Correct 202 ms 1344 KB Output is correct
17 Correct 86 ms 1272 KB Output is correct
18 Correct 65 ms 1160 KB Output is correct
19 Correct 218 ms 2108 KB Output is correct
20 Correct 161 ms 1288 KB Output is correct