Submission #894422

#	Time	Username	Problem	Language	Result	Execution time	Memory
894422		nahco314	Collider (IZhO11_collider)	C++14	100 / 100	210 ms	10564 KiB

collider

#include <bits/stdc++.h>
using namespace std;

mt19937 mt(0);

int find_num(int n, int m, vector<int> &nexts, vector<pair<int, int>>& looks, int num) {
    int start = -1;
    int start_pos = -1;
    for (auto [id, pos] : looks) {
        if (pos <= num) {
            if (start_pos < pos) {
                start = id;
                start_pos = pos;
            }
        }
    }
    for (int i = start_pos; i < num; i++) {
        start = nexts[start];
    }
    return start;
}

int main() {
    int n, m;
    cin >> n >> m;
    string initial_string;
    cin >> initial_string;

    vector<int> nexts(n + 2);
    for (int i = 0; i < n + 2; i++) {
        if (i == n + 1) {
            nexts[i] = -1;
        } else {
            nexts[i] = i + 1;
        }
    }
    vector<int> prevs(n + 2);
    for (int i = 0; i < n + 2; i++) {
        if (i == 0) {
            prevs[i] = -1;
        } else {
            prevs[i] = i - 1;
        }
    }

    vector<pair<int, int>> looks;
    looks.emplace_back(0, 0);
    uniform_int_distribution<> r(0, n - 1);
    for (int i = 0; i * i < n; i++) {
        int t = r(mt);
        looks.emplace_back(t + 1, t + 1);
    }

    for (int i = 0; i < m; i++) {
        char q;
        cin >> q;

        if (q == 'a') {
            int a, b, x, y;
            cin >> a >> b;

            if (a == b) {
                continue;
            }
            
            x = find_num(n, m, nexts, looks, a);
            y = find_num(n, m, nexts, looks, b);

            int px = prevs[x];
            int py = prevs[y];
            int nx = nexts[x];
            int ny = nexts[y];

            if (a < b) {
                nexts[px] = nx;
                prevs[nx] = px;

                nexts[y] = x;
                prevs[x] = y;

                nexts[x] = ny;
                prevs[ny] = x;

                for (int j = 0; j < looks.size(); j++) {
                    if (looks[j].second == a) {
                        looks[j].second = b;
                    } else if (a <= looks[j].second && looks[j].second <= b) {
                        looks[j].second--;
                    }
                }
            } else {
                nexts[py] = x;
                prevs[x] = py;

                nexts[x] = y;
                prevs[y] = x;

                nexts[px] = nx;
                prevs[nx] = px;

                for (int j = 0; j < looks.size(); j++) {
                    if (looks[j].second == a) {
                        looks[j].second = b;
                    } else if (b <= looks[j].second && looks[j].second <= a) {
                        looks[j].second++;
                    }
                }
            }
        } else {
            int num;
            cin >> num;
            int res = find_num(n, m, nexts, looks, num);
            char ans = initial_string[res - 1];
            cout << ans << endl;
        }
    }
}

Compilation message (stderr)

collider.cpp: In function 'int find_num(int, int, std::vector<int>&, std::vector<std::pair<int, int> >&, int)':
collider.cpp:9:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
    9 |     for (auto [id, pos] : looks) {
      |               ^
collider.cpp: In function 'int main()':
collider.cpp:84:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 for (int j = 0; j < looks.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~
collider.cpp:101:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |                 for (int j = 0; j < looks.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100