oj.uz

Submission #515780

# Submission time Handle Problem Language Result Execution time Memory
515780 2022-01-19T16:16:14 Z LouayFarah Lozinke (COCI17_lozinke) C++14
100 / 100
 297 ms 1660 KB 
#include "bits/stdc++.h"

using namespace std;

#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const long long MOD = 998244353;
const long long INF = 1e18;

int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};

ll my_rand(ll l, ll r)
{
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ll len = r-l;
    ll a = rand()%len;
    ll b = rand()%len;

    ll res = ((((a%len)*((RAND_MAX+1)%len))%len) + (b%len))%len;

    if(res<l)
        res +=l;

    return res;
}

bool substring(string sub, string s)
{
    for(int i = 0; i+int(sub.length())-1<int(s.length()); i++)
    {
        bool flag = true;
        for(int j = 0; j<int(sub.length()); j++)
        {
            if(sub[j]!=s[i+j])
            {
                flag = false;
                break;
            }
        }

        if(flag)
            return true;
    }

    return false;
}

bool compare(string &a, string &b)
{
    int lena = int(a.length());
    int lenb = int(b.length());

    if(lena==lenb)
        return a<=b;
    return lena<lenb;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    ll n;
    cin >> n;

    vector<string> arr;
    for(int i = 0; i<n; i++)
    {
        string s;
        cin >> s;

        arr.pb(s);
    }

    sort(arr.begin(), arr.end());


    ll res = 0;

    for(int i = 0; i<n; i++)
    {
        string s = arr[i];
        ll len = int(s.length());
        set<string> visited;
        for(int j = 0; j<len; j++)
        {
            string curr = "";
            for(int k = j; k<len; k++)
            {
                curr.pb(s[k]);
                if(visited.count(curr)==1)
                    continue;
                visited.insert(curr);

                res+=upper_bound(arr.begin(), arr.end(), curr)-lower_bound(arr.begin(), arr.end(), curr);
            }
        }
    }

    cout << res-n << endl;

    return 0;
}

Compilation message

lozinke.cpp: In function 'long long int my_rand(long long int, long long int)':
lozinke.cpp:24:35: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   24 |     ll res = ((((a%len)*((RAND_MAX+1)%len))%len) + (b%len))%len;
      |                                   ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 22 ms 452 KB Output is correct
8 Correct 27 ms 440 KB Output is correct
9 Correct 130 ms 976 KB Output is correct
10 Correct 147 ms 976 KB Output is correct
11 Correct 135 ms 1004 KB Output is correct
12 Correct 275 ms 1104 KB Output is correct
13 Correct 276 ms 1612 KB Output is correct
14 Correct 203 ms 1612 KB Output is correct
15 Correct 297 ms 1632 KB Output is correct
16 Correct 295 ms 1612 KB Output is correct
17 Correct 78 ms 1660 KB Output is correct
18 Correct 63 ms 1612 KB Output is correct
19 Correct 254 ms 1612 KB Output is correct
20 Correct 148 ms 1608 KB Output is correct