oj.uz

Submission #757489

# Submission time Handle Problem Language Result Execution time Memory
757489 2023-06-13T08:59:34 Z dxz05 Vim (BOI13_vim) C++17
0 / 100
 2000 ms 10064 KB 
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

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

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 7e4 + 2;

vector<int> get_dist(const string &s, int pos){
    int n = (int) s.size();

    vector<vector<int>> nxt(n);
    vector<int> last(26, 0);

    for (int i = n - 1; i >= 0; i--){
        nxt[i].assign(26, i);

        for (int j = 0; j < 26; j++){
            nxt[i][j] = last[j];
            if (j == 4) nxt[i][j] = -1;
        }

        last[s[i] - 'a'] = i;
    }

    vector<int> dp(n, 1e9);
    dp[pos] = 0;

    priority_queue<pair<int, int>> pq;
    pq.emplace(0, pos);
    vector<bool> processed(n, false);

    while (!pq.empty()){
        int i = pq.top().second;
        pq.pop();

        if (processed[i]) continue;
        processed[i] = true;

        if (i > 0 && dp[i - 1] > dp[i] + 1){
            dp[i - 1] = dp[i] + 1;
            pq.emplace(-dp[i - 1], i - 1);
        }

        for (int j = 0; j < 26; j++){
            int t = nxt[i][j];
            if (t >= 0 && dp[t] > dp[i] + 2){
                dp[t] = dp[i] + 2;
                pq.emplace(-dp[t], t);
            }
        }

    }

    return dp;
}

void solve(){
    int n; string s;
    cin >> n >> s;

    int pos = 0;
    int ans = 0;

    while (count(all(s), 'e')){
        n = (int) s.size();

        if (s[pos] == 'e'){
            ans++;
            s.erase(s.begin() + pos);
            continue;
        }

        int i = find(all(s), 'e') - s.begin();
        while (i < n && s[i] == 'e') i++;
        i--;

        ans += get_dist(s, pos)[i];
        pos = i;
    }

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:99:13: warning: unused variable 'startTime' [-Wunused-variable]
   99 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 340 KB Output isn't correct
2 Incorrect 15 ms 388 KB Output isn't correct
3 Incorrect 12 ms 340 KB Output isn't correct
4 Incorrect 14 ms 384 KB Output isn't correct
5 Incorrect 14 ms 340 KB Output isn't correct
6 Incorrect 23 ms 340 KB Output isn't correct
7 Incorrect 20 ms 340 KB Output isn't correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 320 KB Output isn't correct
13 Incorrect 25 ms 340 KB Output isn't correct
14 Incorrect 15 ms 340 KB Output isn't correct
15 Incorrect 12 ms 340 KB Output isn't correct
16 Incorrect 14 ms 340 KB Output isn't correct
17 Incorrect 15 ms 340 KB Output isn't correct
18 Incorrect 12 ms 340 KB Output isn't correct
19 Incorrect 11 ms 340 KB Output isn't correct
20 Incorrect 14 ms 324 KB Output isn't correct
21 Incorrect 17 ms 380 KB Output isn't correct
22 Incorrect 15 ms 384 KB Output isn't correct
23 Incorrect 12 ms 340 KB Output isn't correct
24 Incorrect 11 ms 388 KB Output isn't correct
25 Incorrect 13 ms 384 KB Output isn't correct
26 Incorrect 14 ms 320 KB Output isn't correct
27 Incorrect 18 ms 384 KB Output isn't correct
28 Incorrect 22 ms 392 KB Output isn't correct
29 Incorrect 20 ms 376 KB Output isn't correct
30 Incorrect 14 ms 340 KB Output isn't correct
31 Incorrect 12 ms 324 KB Output isn't correct
32 Incorrect 15 ms 340 KB Output isn't correct
33 Incorrect 14 ms 388 KB Output isn't correct
34 Incorrect 18 ms 340 KB Output isn't correct
35 Incorrect 18 ms 340 KB Output isn't correct
36 Incorrect 20 ms 416 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 980 KB Time limit exceeded
2 Execution timed out 2040 ms 1004 KB Time limit exceeded
3 Incorrect 718 ms 724 KB Output isn't correct
4 Execution timed out 2069 ms 980 KB Time limit exceeded
5 Incorrect 1888 ms 1100 KB Output isn't correct
6 Incorrect 1271 ms 1000 KB Output isn't correct
7 Execution timed out 2075 ms 968 KB Time limit exceeded
8 Execution timed out 2079 ms 980 KB Time limit exceeded
9 Execution timed out 2029 ms 1000 KB Time limit exceeded
10 Incorrect 1976 ms 1004 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 8660 KB Time limit exceeded
2 Execution timed out 2013 ms 8532 KB Time limit exceeded
3 Execution timed out 2017 ms 8652 KB Time limit exceeded
4 Execution timed out 2075 ms 9988 KB Time limit exceeded
5 Execution timed out 2065 ms 9940 KB Time limit exceeded
6 Execution timed out 2077 ms 8872 KB Time limit exceeded
7 Execution timed out 2045 ms 9196 KB Time limit exceeded
8 Execution timed out 2074 ms 9300 KB Time limit exceeded
9 Execution timed out 2052 ms 9292 KB Time limit exceeded
10 Execution timed out 2077 ms 9428 KB Time limit exceeded
11 Execution timed out 2048 ms 10048 KB Time limit exceeded
12 Execution timed out 2061 ms 10064 KB Time limit exceeded
13 Execution timed out 2063 ms 9692 KB Time limit exceeded
14 Execution timed out 2077 ms 9808 KB Time limit exceeded
15 Execution timed out 2066 ms 9920 KB Time limit exceeded
16 Execution timed out 2073 ms 8552 KB Time limit exceeded
17 Execution timed out 2045 ms 8680 KB Time limit exceeded
18 Execution timed out 2056 ms 8716 KB Time limit exceeded
19 Execution timed out 2033 ms 8560 KB Time limit exceeded
20 Execution timed out 2071 ms 8652 KB Time limit exceeded