Submission #753749

#	Time	Username	Problem	Language	Result	Execution time	Memory
753749		MilosMilutinovic	Collider (IZhO11_collider)	C++14	0 / 100	1 ms	212 KiB

collider

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
struct Node {
    char val;
    int prior;
    int sz;
    Node *left;
    Node *right;
    Node(char c) {
        val = c;
        prior = rng();
        sz = 1;
        left = nullptr;
        right = nullptr;
    }
} *root;
int get_sz(Node *nd) { return nd == nullptr ? 0 : nd->sz; }
void upd(Node *&nd) { nd->sz = get_sz(nd->left) + get_sz(nd->right) + 1; }
void Merge(Node *&treap, Node *left, Node *right) {
    if (left == nullptr) { treap = right; return; }
    if (right == nullptr) { treap = left; return; }
    if (left->prior > right->prior) {
        Merge(left->right, left->right, right);
        treap = left;
    } else {
        Merge(right->left, left, right->left);
        treap = right;
    }
    upd(treap);
}
void Split(Node *treap, Node *&left, Node *&right, int val) {
    if (treap == nullptr) {
        left = nullptr;
        right = nullptr;
        return;
    }
    if (get_sz(treap->left) < val) {
        Split(treap->right, treap->right, right, val - get_sz(treap->left) - 1);
        left = treap;
    } else {
        Split(treap->left, left, treap->left, val);
        right = treap;
    }
    upd(treap);
}
void dfs(Node *nd) {
    if (nd == nullptr) return;
    dfs(nd->left);
    printf("%c", nd->val);
    dfs(nd->right);
}
const int N = 1e6 + 10;
int n, q;
char s[N];
char Query(int idx) {
    Node *a, *b;
    Split(root, a, b, idx - 1);
    Node *c, *d;
    Split(b, c, d, 1);
    char res = c->val;
    Merge(b, c, d);
    Merge(root, a, b);
    return res;
}
int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        Merge(root, root, new Node(s[i]));
    }
    while (q--) {
        char c;
        scanf("%c", &c);
        while (c < 'a' || c > 'z') {
            scanf("%c", &c);
        }
        if (c == 'a') {
            int i, j;
            scanf("%d%d", &i, &j);
            if (i < j) j--;
            Node *a, *b;
            Split(root, a, b, i - 1);
            Node *c, *d;
            Split(b, c, d, 1);
            Merge(root, a, d);
            Split(root, a, b, j - 1);
            Merge(d, a, c);
            Merge(root, d, b);
        } else {
            int i;
            scanf("%d", &i);
            printf("%c\n", Query(i));
        }
    }
}

Compilation message (stderr)

collider.cpp: In function 'int main()':
collider.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%s", s + 1);
      |     ~~~~~^~~~~~~~~~~~~
collider.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%c", &c);
      |         ~~~~~^~~~~~~~~~
collider.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |             scanf("%c", &c);
      |             ~~~~~^~~~~~~~~~
collider.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |             scanf("%d%d", &i, &j);
      |             ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |             scanf("%d", &i);
      |             ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 100