Submission #1068950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068950		faruk	Text editor (CEOI24_editor)	C++17	0 / 100	0 ms	348 KiB

Main

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    pii f, t;
    cin >> f.first >> f.second;
    f.second--;
    f.first--;
    cin >> t.first >> t.second;
    t.first--;
    t.second--;


    vector<ll> len(n);
    
    for (int i = 0; i < n; i++) {
        cin >> len[i];
    }
    if (*max_element(all(len) - 1) != *min_element(all(len) - 1)) {
        vector<vector<int> > dist(n);
        for (int i = 0; i < n; i++)
            dist[i].resize(len[i] + 1, 1e9);
        
        dist[f.first][f.second] = 0;
        queue<pii> q;
        q.push(f);
        while (!q.empty()) {
            pii curr = q.front(); q.pop();

            vector<pii> nei;
            pii lft = curr;
            if (lft.second > 0)
                lft.second--;
            else if (lft.first != 0)
                lft = pii(lft.first - 1, len[lft.first - 1]);
            
            pii rght = curr;
            if (rght.second < len[rght.first])
                rght.second++;
            else if (rght.first < n - 1)
                rght.second = 0, rght.first++;
            
            pii up = curr;
            if (curr.first != 0)
            {
                up.first--;
                up.second = min(up.second, len[up.first]);
            }

            pii down = curr;
            if (curr.first != n - 1) {
                down.first++;
                down.second = min(down.second, len[down.first]);
            }

            nei = {up, down, rght, lft};
            for (pii guy : nei) {
                if (dist[guy.first][guy.second] != 1e9)
                    continue;
                dist[guy.first][guy.second] = dist[curr.first][curr.second] + 1;
                q.push(guy);
            }
        }
        cout << dist[t.first][t.second] << "\n";
        return 0;
    }
    
    ll f_idx = f.first * len[0] + f.second;
    ll t_idx = t.first * len[0] + t.second;

    if (t.first == n - 1) {
        cout << t.first - f.first << "\n";
        return 0;
    }

    int cnt = 0;
    while (abs(f_idx - t_idx) >= len[0]) {
        if (f_idx > t_idx)
            f_idx -= len[0];
        else
            f_idx += len[0];
        cnt++;
    }

    cnt += min({abs(f_idx - t_idx), abs(f_idx - t_idx + len[0]), abs(f_idx - t_idx - len[0])});

    cout <<cnt << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44