oj.uz

Submission #524494

# Submission time Handle Problem Language Result Execution time Memory
524494 2022-02-09T09:50:57 Z Jarif_Rahman Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 108884 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<str> lex(str s){
    int n = s.size();
    char a = *min_element(s.begin(), s.end());
    vector<int> c;
    for(int i = 0; i < n; i++) if(s[i] == a) c.pb(i);
    
    vector<str> rt;

    auto startswith = [&s, &n](int k){
        str rt = "";
        for(int i = k; i < n; i++) rt+=s[i];
        for(int i = 0; i < k; i++) rt+=s[i];
        return rt;
    };

    if(c.size() == 1) return {startswith(c[0])};

    int mn = 1e9, k = -1;
    for(int i = 0; i < c.size(); i++){
        int ii = (i+1)%c.size();
        int cur = c[i]+1;
        cur+=n-c[ii];
        if(cur < mn) mn = cur, k = ii;
    }

    if(s.size()%2 == 0 && s.size()/2 == mn-1){
        return {startswith(c[k]), startswith(c[(k-1+c.size())%c.size()])};
    }
    else return {startswith(c[k])};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    str s1, s2; cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();

    unordered_map<str, pair<int, int>> mp;

    for(int i = 0; i < n; i++) for(int j = i; j < n; j++){
        str ss = "";
        for(int k = i; k <= j; k++) ss+=s1[k];
        for(str h: lex(ss)){
            if(mp.find(h) == mp.end() || mp[h].f < j-i+1) mp[h] = {j-i+1, i};
        }
        reverse(ss.begin(), ss.end());
        for(str h: lex(ss)){
            if(mp.find(h) == mp.end() || mp[h].f < j-i+1) mp[h] = {j-i+1, i};
        }
    }

    int ans = 0, a = 0, b = 0;

    for(int i = 0; i < m; i++) for(int j = i; j < m; j++){
        str ss = "";
        for(int k = i; k <= j; k++) ss+=s2[k];
        for(auto h: lex(ss)){
            if(mp[h].f > ans) ans = mp[h].f, a = mp[h].sc, b = i;
        }
        reverse(ss.begin(), ss.end());
        for(auto h: lex(ss)){
            if(mp[h].f > ans) ans = mp[h].f, a = mp[h].sc, b = i;
        }
    }

    cout << ans << "\n";
    cout << a << " " << b << "\n";
}

Compilation message

necklace.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > lex(str)':
necklace.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < c.size(); i++){
      |                    ~~^~~~~~~~~~
necklace.cpp:34:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(s.size()%2 == 0 && s.size()/2 == mn-1){
      |                           ~~~~~~~~~~~^~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 836 KB Output is correct
2 Correct 18 ms 964 KB Output is correct
3 Correct 13 ms 700 KB Output is correct
4 Correct 14 ms 1240 KB Output is correct
5 Correct 18 ms 2316 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 836 KB Output is correct
2 Correct 18 ms 964 KB Output is correct
3 Correct 13 ms 700 KB Output is correct
4 Correct 14 ms 1240 KB Output is correct
5 Correct 18 ms 2316 KB Output is correct
6 Correct 957 ms 18460 KB Output is correct
7 Correct 792 ms 31864 KB Output is correct
8 Correct 547 ms 7184 KB Output is correct
9 Correct 853 ms 36264 KB Output is correct
10 Correct 862 ms 64812 KB Output is correct
11 Correct 860 ms 63804 KB Output is correct
12 Correct 699 ms 34956 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 836 KB Output is correct
2 Correct 18 ms 964 KB Output is correct
3 Correct 13 ms 700 KB Output is correct
4 Correct 14 ms 1240 KB Output is correct
5 Correct 18 ms 2316 KB Output is correct
6 Correct 957 ms 18460 KB Output is correct
7 Correct 792 ms 31864 KB Output is correct
8 Correct 547 ms 7184 KB Output is correct
9 Correct 853 ms 36264 KB Output is correct
10 Correct 862 ms 64812 KB Output is correct
11 Correct 860 ms 63804 KB Output is correct
12 Correct 699 ms 34956 KB Output is correct
13 Execution timed out 1584 ms 108884 KB Time limit exceeded
14 Halted 0 ms 0 KB -