oj.uz

답안 #1078061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078061 2024-08-27T12:09:48 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
90 / 100
 146 ms 3788 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=2e4+5, mod=1e9+7;
 
#define ll long long
 
ll n, c[nx][12], sz[nx], res, p[nx], vl[nx];
string s;
map<ll, ll> mp;
 
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    p[0]=1;
    for (int i=1; i<=10; i++) p[i]=(p[i-1]*30)%mod;
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>s;
        sz[i]=s.size();
        for (int j=1; j<=sz[i]; j++) c[i][j]=s[j-1]-'a'+1;
    }
    for (int i=1; i<=n; i++)
    {
        set<ll> s;
        for (int j=1; j<=sz[i]; j++)
        {
            ll tmp=0;
            for (int k=j; k<=sz[i]; k++)
            {
                tmp=(tmp+c[i][k]*p[k-j])%mod;
                s.insert(tmp);
                if (j==1&&k==sz[i]) vl[i]=tmp;
            }
        }
        for (auto x:s) if (mp.find(x)!=mp.end()) res+=mp[x];
        mp[vl[i]]++;
    }
    mp.clear();
    for (int i=n; i>=1; i--)
    {
        set<ll> s;
        for (int j=1; j<=sz[i]; j++)
        {
            ll tmp=0;
            for (int k=j; k<=sz[i]; k++)
            {
                tmp=(tmp+c[i][k]*p[k-j])%mod;
                s.insert(tmp);
            }
        }
        for (auto x:s) if (mp.find(x)!=mp.end()) res+=mp[x];
        mp[vl[i]]++;
    }
    cout<<res;
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 5 ms 480 KB Output is correct
6 Correct 8 ms 720 KB Output is correct
7 Correct 12 ms 600 KB Output is correct
8 Correct 11 ms 600 KB Output is correct
9 Correct 50 ms 1884 KB Output is correct
10 Correct 61 ms 1884 KB Output is correct
11 Correct 83 ms 2644 KB Output is correct
12 Incorrect 142 ms 2704 KB Output isn't correct
13 Correct 128 ms 3412 KB Output is correct
14 Correct 146 ms 3788 KB Output is correct
15 Incorrect 140 ms 3584 KB Output isn't correct
16 Correct 110 ms 2912 KB Output is correct
17 Correct 28 ms 2756 KB Output is correct
18 Correct 21 ms 2832 KB Output is correct
19 Correct 135 ms 3332 KB Output is correct
20 Correct 76 ms 2896 KB Output is correct