Submission #515780

#	Time	Username	Problem	Language	Result	Execution time	Memory
515780		LouayFarah	Lozinke (COCI17_lozinke)	C++14	100 / 100	297 ms	1660 KiB

lozinke

#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 (stderr)

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 / 100