Submission #1184619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184619		razivo	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	5 / 85	263 ms	484 KiB

necklace

#include <iostream>
#include <map>
#include<vector>
typedef __int128 ll;
#include <string>
using namespace std;
const int depth = 30;
const ll base = 2;
const ll mod = 1000000007LL;
vector<ll> ra;
vector<pair<ll,int>> cychash(vector<ll> &v, int t) {
    ll init = 0;
    vector<pair<ll,int>> res;
    for (int k = 0; k < t; ++k) {
        ll val = 1;
        for (int j = 0; j < depth; ++j) {
            init += ((v[k]*v[(k+(ra[j]%t))%t])%mod)*val;
            init%=mod;
            val*=base;
            val%=mod;
        }
    }
    res.push_back({init,0});
    for (int i = 0; i < v.size()-t; ++i) {
        ll val = 1;
        for (int j = 0; j < depth; ++j) {
            init -= (((v[i]*v[i+(ra[j]%t)])%mod)*val)%mod;
            init -= (((v[i]*v[i+t-(ra[j]%t)])%mod)*val)%mod;
            init+=mod;
            init%=mod;
            init+=(((v[i-(ra[j]%t)+t]*v[i+t])%mod)*val)%mod;
            init+=(((v[i+(ra[j]%t)]*v[i+t])%mod)*val)%mod;
            init%=mod;
            val*=base;
            val%=mod;
        }
        res.push_back({init,i+1});
    }
    return res;
}
pair <int,int> compare(vector<pair<ll,int>> &a, vector<pair<ll,int>> &b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0,j=0;
    while(i!=a.size() && j!=b.size()) {
        if(a[i].first==b[j].first) return {a[i].second,b[j].second};
        if(a[i].first>b[j].first) j++;
        else i++;
    }
    return {-1,-1};
}
int main() {
    string s1,s2;
    cin>>s1>>s2;
    int n = s1.size();
    int m = s2.size();
    vector<ll> v1,v2;
    for (int i = 0; i < depth; ++i) {
        ra.push_back(rand());
    }
    for (int i = 0; i < n; ++i) {
        v1.push_back((ra[(s1[i]-'a')]));
    }
    for (int i = 0; i < m; ++i) {
        v2.push_back((ra[(s2[i]-'a')]));
    }

    int t = min(m,n);

    for (int i = t; i > 0; --i) {
        auto a = cychash(v1,i);
        auto b = cychash(v2,i);
        auto c = compare(a,b);
        pair<int,int> u = {-1,-1};
        if(c!= u) {
            cout<< i <<endl;
            cout<<c.first<<" "<<c.second<<endl;
            exit(0);
        }
    }
    int stop = 1;
}

• Subtask 1: 5 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40