oj.uz

Submission #656221

# Submission time Handle Problem Language Result Execution time Memory
656221 2022-11-06T14:51:25 Z Do_you_copy Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 232 ms 556 KB 
#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
 
ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}
 
ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}
 
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;
int n, m;
string rt;
void kmp(const string &s, vector <int> &p){
    int _n = s.length();
    p.resize(_n);
    p[0] = -1;
    for (int i = 1, j = -1; i < _n; ++i){
        while (j > -1 && s[j + 1] != s[i]){
            j = p[j];
        }
        if (s[j + 1] == s[i]) ++j;
        p[i] = j;
    }
}
 
tuple <int, int, int> get_ans(const string &s, const string &t, bool flag = 0){
    tuple <int, int, int> ans = {0, 0, 0};
    n = s.length(), m = t.length();
    for (int i = 0; i < n; ++i){
        vector <int> p1, p2;
        string s1 = s.substr(0, i);
        string s2 = s.substr(i, n - i);
        reverse(s1.begin(), s1.end());
        kmp(s1 + "#" + t, p1);
        kmp(s2 + "#" + rt, p2);
        for (int j = 0; j < m; ++j){
            ans = max(ans, {p1[i + j + 1] + p2[n + m - i - j - 1] + 2,
                      i - p1[i + j + 1] - 1,
                      flag ? m - j - 2 - p2[n + m - i - j - 1] : j - p1[i + j + 1]});
        }
    }
    return ans;
}
 
void Init(){
    string s, t;
    cin >> s >> t;
    rt = t;
    reverse(rt.begin(), rt.end());
    tuple <int, int, int> ans = get_ans(s, t);
    swap(t, rt);
    ans = max(ans, get_ans(s, t, 1));
    cout << get<0>(ans) << " " << get<1>(ans) << " " << get<2>(ans) << "\n";
}
 
#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 6 ms 364 KB Output is correct
12 Correct 5 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 6 ms 364 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 226 ms 432 KB Output is correct
14 Correct 194 ms 440 KB Output is correct
15 Correct 210 ms 556 KB Output is correct
16 Correct 176 ms 460 KB Output is correct
17 Correct 222 ms 432 KB Output is correct
18 Correct 232 ms 444 KB Output is correct
19 Correct 206 ms 436 KB Output is correct
20 Correct 215 ms 484 KB Output is correct
21 Correct 210 ms 404 KB Output is correct