oj.uz

Submission #1006116

# Submission time Handle Problem Language Result Execution time Memory
1006116 2024-06-23T12:26:18 Z AverageAmogusEnjoyer Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 436 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    string s,t;
    cin >> s >> t;
    int n = (int)s.size();
    int ans = 0;
    int a = 0,b = 0;
    auto search = [&](bool sw) {
        for (int i=0;i<n;i++) {
            for (int j=i;j<n;j++) {
                for (int k=i;k>=0;k--) {
                    string r = s.substr(i,j-i+1);
                    string f = s.substr(k,i-k);
                    r += f;
                    auto z = t.find(r);
                    if (z != string::npos && cmax(ans,(int)r.size())) {
                        /*
                        cout << "s = " << s << endl;
                        cout << "t = " << t << endl;
                        cout << "r = " << r << endl;
                        cout << "find = " << t.find(r) << endl;
                        */
                        a = k;
                        b = (sw ? (int)t.size() - (z + (int)r.size()) : z);
                    }
                }
            }
        }
    };
    search(false);
    reverse(t.begin(),t.end());
    search(true);
    assert(ans);
    cout << ans << endl << a << " " << b << endl;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 344 KB Output is correct
2 Correct 53 ms 420 KB Output is correct
3 Correct 51 ms 348 KB Output is correct
4 Correct 48 ms 436 KB Output is correct
5 Correct 22 ms 348 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 344 KB Output is correct
2 Correct 53 ms 420 KB Output is correct
3 Correct 51 ms 348 KB Output is correct
4 Correct 48 ms 436 KB Output is correct
5 Correct 22 ms 348 KB Output is correct
6 Execution timed out 1520 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 344 KB Output is correct
2 Correct 53 ms 420 KB Output is correct
3 Correct 51 ms 348 KB Output is correct
4 Correct 48 ms 436 KB Output is correct
5 Correct 22 ms 348 KB Output is correct
6 Execution timed out 1520 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -