Submission #894422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894422	2023-12-28T09:08:35 Z	nahco314	Collider (IZhO11_collider)	C++14	100 / 100	210 ms	10564 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	9 ms	348 KB	Output is correct
3	Correct	31 ms	1732 KB	Output is correct
4	Correct	69 ms	8464 KB	Output is correct
5	Correct	123 ms	8468 KB	Output is correct
6	Correct	163 ms	9492 KB	Output is correct
7	Correct	170 ms	10528 KB	Output is correct
8	Correct	92 ms	10420 KB	Output is correct
9	Correct	210 ms	10564 KB	Output is correct
10	Correct	141 ms	10500 KB	Output is correct