Submission #961866

#	Time	Username	Problem	Language	Result	Execution time	Memory
961866		idas	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	9 / 85	1538 ms	600 KiB

necklace

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) ((int)((x).size()))
#define le(vec) vec[vec.size()-1]
#define all(x) (x).begin(), (x).end()
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=3010, C=9973;
string a, b; int n, m;
bool v[N];

string ga(int x, int y)
{
    int ln=y-x+1;

    int in=x, i=x;
    FOR(add, 1, ln+1)
    {
        int j=add%ln+x;
        if(a[j]<a[i]) in=i=j;
        else if(a[j]>a[i]) i=in;
        else i=(i-x+1)%ln+x;
    }

    string ret="";
    FOR(add, 0, ln)
    {
        ret+=a[(in+add-x)%ln+x];
    }

    return ret;
}

string gb(int x, int y)
{
    int ln=y-x+1;

    int in=x, i=x;
    FOR(add, 1, ln+1)
    {
        int j=add%ln+x;
        if(b[j]<b[i]) in=i=j;
        else if(b[j]>b[i]) i=in;
        else i=(i-x+1)%ln+x;
    }

    string ret="";
    FOR(add, 0, ln)
    {
        ret+=b[(in+add-x)%ln+x];
    }

    return ret;
}

string gre(int x, int y)
{
    int ln=y-x+1;

    int in=x, i=x;
    FOR(add, 1, ln+1)
    {
        int j=ln-add+x;
        if(b[j]<b[i]) in=i=j;
        else if(b[j]>b[i]) i=in;
        else i=(i-x-1+ln)%ln+x;
    }

    string ret="";
    FOR(add, 0, ln)
    {
        ret+=b[(in-add-x+ln)%ln+x];
    }

    return ret;
}

int ha(string s)
{
    ll ret=0, pw=1;
    FOR(i, 0, sz(s))
    {
        ret+=(s[i]-'a')*pw%MOD; ret%=MOD;
        pw*=C;
        pw%=MOD;
    }
    return ret;
}

int main()
{
    setIO();
    cin >> a >> b; n=sz(a); m=sz(b);

    for(int ln=n; ln>=1; ln--){
        set<pii> st;
        FOR(i, 0, n)
        {
            int j=i+ln-1; if(j>=n) break;

            string now=ga(i, j);

//            cout << i << " " << j << ": " << now << '\n';

            st.insert({ha(now),i});
        }

        FOR(i, 0, m)
        {
            int j=i+ln-1; if(j>=m) break;

            string now=gb(i, j);

            int hsh=ha(now);
            auto it=st.lower_bound({hsh,0});

            if(it!=st.end() && (*it).f==hsh){
                cout << ln << '\n';
                cout << (*it).s << " " << i;
                return 0;
            }

            now=gre(i, j);

            hsh=ha(now);
            it=st.lower_bound({hsh,0});

            if(it!=st.end() && (*it).f==hsh){
                cout << ln << '\n';
                cout << (*it).s << " " << i;
                return 0;
            }
        }
    }
}
/*
zxyabcd
yxbadctz
*/

Compilation message (stderr)

necklace.cpp: In function 'void setIO(std::string)':
necklace.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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