oj.uz

답안 #1078145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078145 2024-08-27T13:19:58 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
0 / 100
 4 ms 1628 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int , int>
#define fi first
#define se second
#define endl '\n'
const int INF = (int)1e9;
const int maxn = 20000 + 6;
const int mod = 1e9 + 7;

int n;

string a[maxn];

const int base = 311;
const int nmod = 2;
const int ModHash[4] = {(int)1e9 + 2277 , (int)1e9 + 5277 , (int)1e9 + 8277 , (int)1e9 + 9277};

ll pw[maxn][nmod];

void prepare(int n)
{

    for (int i = 0 ; i < nmod ; ++i) pw[0][i] = 1;

    for (int i = 1 ; i <= n ; ++i)
        for (int j = 0 ; j < nmod ; ++j) pw[i][j] = pw[i - 1][j] * base % ModHash[j];

}

struct HASH{

    vector<vector<ll>> HashVal;

    void BuildHash(string s)
        {

            int n = s.size();

            HashVal.resize(n + 1);

            for (int i = 0 ; i <= n ; ++i) HashVal[i].resize(nmod);

            for (int i = 1 ; i <= n ; ++i)
                for (int j = 0 ; j < nmod ; ++j)
                    HashVal[i][j] =( HashVal[i - 1][j] * base + (int)s[i - 1]) % ModHash[j];

        }
    
    ll get(int l , int r , int pos)
        {

            return (HashVal[r][pos] - HashVal[l - 1][pos] * pw[r - l + 1][pos] % ModHash[pos] + ModHash[pos]) % ModHash[pos];

        }

} h[maxn];

map<pii , int> m;

ll ans = 0;


void calc(int id)
{
    int n = a[id].size();

    map<pii , bool> mark;

    for (int i = 1 ; i <= n ; ++i)
        for (int j = i ; j <= n ; ++j)
            {   
                if ( mark[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}] == 0)
                    {
                        ans += m[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}];
                        mark[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}] = 1;
                    }
                // if (m[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}])
                //     cout << id << " " << i << " " << j << " " << ans << endl;
            }

    m[{ h[id].get(1 , n , 0) , h[id].get(1 , n , 1) } ]++;
    // cerr <<   id << " " << m[{ h[3].get(1 , 1 , 0) , h[3].get(1 , 1 , 1) } ] << " " << m[{ h[1].get(1 , 1 , 0) , h[1].get(1 , 1 , 1) } ]<< endl;
    // cerr << a[3][0] << " " << a[1][0] << endl;

}


int main()
{

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

    freopen("PASS.INP" , "r" , stdin);
    freopen("PASS.OUT" , "w" , stdout);
    
    prepare(15);


    cin >> n ;

    for (int i = 1 ; i <= n ; ++i) cin >> a[i];

    sort(a + 1 , a + n + 1 , [&](string a , string b)
        {
            return (a.size() != b.size() ? a.size() < b.size() : a < b);
        });

    // for (int i = 1 ; i <= n ; ++i) cout << a[i] << endl;

    for (int i = 1 ; i <= n ; ++i) h[i].BuildHash(a[i]);

    for (int i = 1 ; i <= n ; ++i) calc(i);
    
    

    for (int i = 1 ; i <= n ; ++i) 
        {
            int cnt = m[{ h[i].get(1 , a[i].size() , 0) , h[i].get(1 , a[i].size() , 1) } ];

            ans += (cnt - 1);
            m[{ h[i].get(1 , a[i].size() , 0) , h[i].get(1 , a[i].size() , 1) } ]--;

        }
    
    
    cout << ans << endl;
    
    return 0;

}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen("PASS.INP" , "r" , stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen("PASS.OUT" , "w" , stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1624 KB Output isn't correct
2 Incorrect 2 ms 1628 KB Output isn't correct
3 Incorrect 4 ms 1372 KB Output isn't correct
4 Incorrect 2 ms 1628 KB Output isn't correct
5 Incorrect 2 ms 1628 KB Output isn't correct
6 Incorrect 4 ms 1628 KB Output isn't correct
7 Incorrect 2 ms 1628 KB Output isn't correct
8 Incorrect 2 ms 1628 KB Output isn't correct
9 Incorrect 3 ms 1628 KB Output isn't correct
10 Incorrect 3 ms 1628 KB Output isn't correct
11 Incorrect 2 ms 1628 KB Output isn't correct
12 Incorrect 2 ms 1628 KB Output isn't correct
13 Incorrect 2 ms 1624 KB Output isn't correct
14 Incorrect 2 ms 1628 KB Output isn't correct
15 Incorrect 2 ms 1628 KB Output isn't correct
16 Incorrect 2 ms 1628 KB Output isn't correct
17 Incorrect 2 ms 1628 KB Output isn't correct
18 Incorrect 2 ms 1628 KB Output isn't correct
19 Incorrect 2 ms 1624 KB Output isn't correct
20 Incorrect 4 ms 1628 KB Output isn't correct