Submission #683302

#	Time	Username	Problem	Language	Result	Execution time	Memory
683302		KiriLL1ca	Collider (IZhO11_collider)	C++17	0 / 100	2 ms	1884 KiB

collider

#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]);
        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 = 'a';
                        while (uk < nb) {
                                if (i < sz(st[uk])) {
                                        c = st[uk][i];
                                        st[uk].erase(st[uk].begin() + i);
                                        break;
                                }
                                i -= sz(st[uk++]);
                        }
                        bool ins = 0;
                        uk = 0;
                        while (uk < nb) {
                                if (j < sz(st[uk])) {
                                        st[uk].insert(st[uk].begin() + j, c);
                                        ins = 1;
                                        break;
                                }
                                j -= sz(st[uk++]);
                        }
                        if (!ins) st[uk].insert(st[uk].begin() + j, c), ++nb;
                }
                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();
                                }
                        }
                        while (!sz(st[nb - 1])) --nb;
                }
                ++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
//                freopen("collider.in", "r", stdin);
//                freopen("collider.out", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

• Subtask 1: 0 / 100