oj.uz

Submission #938526

# Submission time Handle Problem Language Result Execution time Memory
938526 2024-03-05T08:54:45 Z stefdasca Lozinke (COCI17_lozinke) C++14
100 / 100
 305 ms 16776 KB 
/*
 
 At Most 10 lowercase letters of the English Alphabet -> We should think in terms of the alphabet and the orientation
 What is the fastest, most efficient way to check if one string is a subset of another
 Of course there isn't some magical way to compare two strings. The solution: Don't compare two strings. Have a frequency array of how many each substring appears
  
 */
#include <iostream>
#include <string>
#include <utility>
#include <string>
#include <map>
 
using namespace std;
 
int n;
string str[20005];
map<string, int> mp;
 
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> str[i];
        map<string, int> temp;
        for(int j = 0; j < str[i].size(); j++) {
            for(int k = j; k < str[i].size(); k++) {
                string exp;
                for(int l = j; l <= k; l++) {
                    exp += str[i][l];
                }
                temp[exp] = 1;
            }
        }
        for (const auto &p : temp) {
            // Now you can access the key using p.first and the value using p.second
            mp[p.first] ++; // Example operation
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans += mp[str[i]] -1;
    }
    cout << ans;
    
    return 0;
}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int j = 0; j < str[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
lozinke.cpp:26:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for(int k = j; k < str[i].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 7 ms 1420 KB Output is correct
6 Correct 11 ms 1368 KB Output is correct
7 Correct 14 ms 2084 KB Output is correct
8 Correct 24 ms 2936 KB Output is correct
9 Correct 59 ms 2640 KB Output is correct
10 Correct 119 ms 7768 KB Output is correct
11 Correct 97 ms 4868 KB Output is correct
12 Correct 271 ms 16776 KB Output is correct
13 Correct 175 ms 2652 KB Output is correct
14 Correct 195 ms 15056 KB Output is correct
15 Correct 305 ms 16380 KB Output is correct
16 Correct 182 ms 1296 KB Output is correct
17 Correct 57 ms 1360 KB Output is correct
18 Correct 36 ms 1112 KB Output is correct
19 Correct 189 ms 8628 KB Output is correct
20 Correct 90 ms 1284 KB Output is correct