oj.uz

Submission #683900

# Submission time Handle Problem Language Result Execution time Memory
683900 2023-01-19T15:05:43 Z KiriLL1ca Collider (IZhO11_collider) C++17
100 / 100
 38 ms 4176 KB 
#include <bits/stdc++.h>
#define vec vector
#define forn(i, s, f) for (int i = s; i <= f; ++i)
#define pb push_back
#define sz(x) (int)((int)(x).size())
#define endl '\n'

using namespace std;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef pair <int, int> pii;

const int N = 1e6 + 10;
const int buben = 1020;

int id[N];
deque <char> st[buben];

inline void solve () {
        int n, q; cin >> n >> q;
        string s; cin >> s;
        for (int i = 0; i < n; ++i) st[i / buben].pb(s[i]);
        const int nb = (n + buben - 1) / buben;
        int iter = 0;

        while (q--) {
                char t; cin >> t;
                if (t == 'a') {
                        int i, j; cin >> i >> j; --i, --j;
                        int uk = 0;
                        char c;
                        while (uk < nb) {
                                if (i < sz(st[uk])) {
                                        c = st[uk][i];
                                        st[uk].erase(st[uk].begin() + i);
                                        break;
                                }
                                i -= sz(st[uk++]);
                        }
                        uk = 0;
                        while (uk < nb) {
                                if (j <= sz(st[uk])) {
                                        st[uk].insert(st[uk].begin() + j, c);
                                        break;
                                }
                                j -= sz(st[uk++]);
                        }
                }
                else {
                        int i; cin >> i; --i;
                        int uk = 0;
                        while (uk < nb) {
                                if (i < sz(st[uk])) {
                                        cout << st[uk][i] << endl;
                                        break;
                                }
                                i -= sz(st[uk++]);
                        }
                }

                if (iter % buben == 0) {
                        for (int i = 0; i + 1 < nb; ++i) {
                                while (sz(st[i]) < buben) {
                                        st[i].pb(st[i + 1][0]);
                                        st[i + 1].pop_front();
                                }
                                while (sz(st[i]) > buben) {
                                        st[i + 1].push_front(st[i].back());
                                        st[i].pop_back();
                                }
                        }
                }
                ++iter;
        }
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #else
                
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 4 ms 1288 KB Output is correct
4 Correct 15 ms 3424 KB Output is correct
5 Correct 23 ms 3492 KB Output is correct
6 Correct 30 ms 3848 KB Output is correct
7 Correct 31 ms 4164 KB Output is correct
8 Correct 19 ms 3944 KB Output is correct
9 Correct 38 ms 4176 KB Output is correct
10 Correct 29 ms 4092 KB Output is correct