oj.uz

Submission #1073385

# Submission time Handle Problem Language Result Execution time Memory
1073385 2024-08-24T13:53:29 Z ProtonDecay314 Text editor (CEOI24_editor) C++17
14 / 100
 4000 ms 323624 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll; // ! CAREFUL
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef pair<int, int> pi;
typedef vector<bool> vb;
#define fi first
#define se second
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false)
#define pb push_back

ll solve(ll n, ll sl, ll sc, ll el, ll ec, const vll& l) {
    vll prefl(n + 1, 0);

    for(ll i = 0; i < n; i++) {
        prefl[i + 1] = prefl[i] + l[i];
    }

    ll totn = prefl[n];

    set<ll> vis;

    typedef pair<ll, pll> ppll;
    typedef vector<ppll> vppll;

    // priority_queue<ppll, vppll, greater<ppll>> pq;
    queue<ppll> pq;

    ll s = prefl[sl] + sc, e = prefl[el] + ec;

    ll ans = 0;

    pq.push({0, {sl, sc}});

    while(!pq.empty()) {
        auto [cdist, curi] = pq.front();

        pq.pop();

        auto [li, ci] = curi;
        ll i = prefl[li] + ci;

        if(vis.count(i) > 0) continue;
        vis.insert(i);
        if(i == e) {
            ans = cdist;
            break;
        }

        // can move up
        if(li > 0) {
            pq.push({cdist + 1, {li - 1, min(ci, l[li - 1] - 1)}});
        }

        // can move down
        if(li < n - 1) {
            pq.push({cdist + 1, {li + 1, min(ci, l[li + 1] - 1)}});
        }

        // can move left
        if(i > 0) {
            if(ci > 0) {
                pq.push({cdist + 1, {li, ci - 1}});
            } else {
                pq.push({cdist + 1, {li - 1, l[li - 1] - 1}});
            }
        }

        // can move right
        if(i < totn - 1) {
            if(ci < l[li] - 1) {
                pq.push({cdist + 1, {li, ci + 1}});
            } else {
                pq.push({cdist + 1, {li + 1, 0}});
            }
        }
    }

    return ans;
}

int main() {
    IOS;

    ll n;
    cin >> n;

    ll sl, sc;
    ll el, ec;
    cin >> sl >> sc;
    cin >> el >> ec;

    sl--; sc--;
    el--; ec--;

    vll l(n, 0);

    for(ll& lv : l) {
        cin >> lv;
        lv++; // ! WARNING, already added one
    }

    cout << solve(n, sl, sc, el, ec, l) << endl;
    
    return 0;
}

Compilation message

Main.cpp: In function 'll solve(ll, ll, ll, ll, ll, const vll&)':
Main.cpp:34:8: warning: unused variable 's' [-Wunused-variable]
   34 |     ll s = prefl[sl] + sc, e = prefl[el] + ec;
      |        ^
Main.cpp:29:26: warning: typedef 'vppll' locally defined but not used [-Wunused-local-typedefs]
   29 |     typedef vector<ppll> vppll;
      |                          ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 4094 ms 323624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 38 ms 4428 KB Output is correct
5 Correct 68 ms 7252 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 177 ms 16732 KB Output is correct
8 Correct 3797 ms 234860 KB Output is correct
9 Correct 2258 ms 116388 KB Output is correct
10 Correct 1925 ms 105552 KB Output is correct
11 Correct 2424 ms 127056 KB Output is correct
12 Correct 1424 ms 89128 KB Output is correct
13 Correct 2827 ms 158620 KB Output is correct
14 Correct 602 ms 49160 KB Output is correct
15 Correct 64 ms 6744 KB Output is correct
16 Correct 92 ms 9500 KB Output is correct
17 Correct 950 ms 71124 KB Output is correct
18 Correct 1360 ms 82260 KB Output is correct
19 Correct 1121 ms 117840 KB Output is correct
20 Correct 1222 ms 73852 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 4094 ms 323624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 4094 ms 323624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 4094 ms 323624 KB Time limit exceeded
5 Halted 0 ms 0 KB -