Submission #1069008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069008		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;

vector<ll> len;
ll n;
ll f_idx, t_idx;

ll wiggle(ll f_idx) {
    ll to_add = abs(f_idx - t_idx);
    to_add = min(to_add, abs(min(f_idx + len[0], len[0]*((ll)n - 1)) - t_idx) + 1);
    if (f_idx - len[0] >= 0)
        to_add = min(to_add, abs(max(0LL, f_idx - len[0]) - t_idx) + 1);
    return to_add;
}

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--;


    len.resize(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;
    }*/
    
    len[0]++;
    f_idx = f.first * (len[0]) + f.second;
    t_idx = t.first * (len[0]) + t.second;

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

    ll cnt = 0;
    ll possible = abs(f_idx - t_idx);
    
    while (abs(f_idx - t_idx) >= len[0]) {
        if (f_idx >= t_idx)
            f_idx -= len[0];
        else
            f_idx += len[0];
        cnt++;
        possible = min(possible, cnt + wiggle(f_idx));
    }

    ll to_add = min(to_add, wiggle(f_idx));
    to_add = min(to_add, 1 + wiggle(min(f_idx + len[0], len[0]*((ll)n - 1))));
    if (f_idx > len[0])
        to_add = min(to_add, 1 + wiggle(f_idx - len[0]));

    cout << min(cnt + to_add, possible) << "\n";

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:8: warning: 'to_add' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |     ll to_add = min(to_add, wiggle(f_idx));
      |        ^~~~~~

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