oj.uz

Submission #937702

# Submission time Handle Problem Language Result Execution time Memory
937702 2024-03-04T11:37:08 Z zwezdinv Modern Machine (JOI23_ho_t5) C++17
11 / 100
 157 ms 9056 KB 
#include <bits/stdc++.h>

std::string process(std::string c, int k) {
        c[k] = 'R';
        std::vector<int> lr, rl;
        for (int i = 0; i < k; ++i) {
                if (c[i] == 'R') lr.push_back(i);
        }
        for (int i = k + 1; i < c.size(); ++i) {
                if (c[i] == 'B') rl.push_back(i);
        }
        if (lr.size() >= rl.size()) {
                int k = rl.size();
                int pos = lr[lr.size() - k];
                for (int i = pos; i < c.size(); ++i) c[i] = 'B';
        } else {
                int k = lr.size();
                int pos = rl[k - 1];
                for (int i = 0; i <= pos; ++i) c[i] = 'R';
        }
        return c;
}

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n, m;
        std::cin >> n >> m;
        std::string c;
        std::cin >> c;
        std::vector<int> a(m);
        for (auto& i : a) std::cin >> i, --i;
        if (n <= 10) {
                int st = 0;
                for (int i = 0; i < n; ++i) {
                        st |= (c[i] == 'R') << i;
                }
                std::vector<std::vector<int>> ss(1 << n, std::vector<int>(n));
                for (int mask = 0; mask < 1 << n; ++mask) {
                        for (int i = 0; i < n; ++i) {
                                int m4sk = mask;
                                int ptr = i;
                                m4sk |= 1 << i;
                                while (0 <= ptr && ptr < n) {
                                        m4sk ^= 1 << ptr;
                                        if (~m4sk >> ptr & 1) {
                                                ptr++;
                                        } else {
                                                ptr--;
                                        }
                                }
                                ss[mask][i] = m4sk;
                        }
                }
                std::vector<int> qq(1 << n, -1);
                std::vector<int> pos(m, -1);
                std::vector<int> leader(m, -1);
                std::vector<std::vector<std::pair<int, int>>> que(m);
                int q;
                std::cin >> q;
                std::vector<int> ans(q);
                for (int i = 0; i < q; ++i) {
                        int l, r;
                        std::cin >> l >> r;
                        --l, --r;
                        que[r].emplace_back(l, i);
                }
                auto get = [&](int u) -> int {
                        while (u != leader[u]) u = leader[u] = leader[leader[u]];
                        return u;
                }; 
                for (int i = 0; i < m; ++i) {
                        if (qq[st] == -1) {
                                qq[st] = i;
                                pos[i] = st;
                                leader[i] = i;
                        } else {
                                leader[i] = qq[st];
                        }
                        std::vector<int> nw(1 << n, -1);
                        for (int j = 0; j < 1 << n; ++j) {
                                if (qq[j] == -1) continue;
                                int k = ss[j][a[i]];
                                if (nw[k] != -1) {
                                        leader[qq[j]] = nw[k];
                                } else {
                                        nw[k] = qq[j];
                                        pos[qq[j]] = k;
                                }
                        }
                        qq = nw;
                        for (auto [l, id] : que[i]) {
                                ans[id] = __builtin_popcount(pos[get(l)]);
                        }
                }
                for (auto i : ans) std::cout << i << '\n';
        } else {
                int q;
                std::cin >> q;
                int l, r;
                std::cin >> l >> r;
                --l, --r;
                for (int i = l; i <= r; ++i) {
                        c = process(c, a[i]);
                }
                std::cout << std::count(c.begin(), c.end(), 'R');
        }
}

Compilation message

Main.cpp: In function 'std::string process(std::string, int)':
Main.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         for (int i = k + 1; i < c.size(); ++i) {
      |                             ~~^~~~~~~~~~
Main.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |                 for (int i = pos; i < c.size(); ++i) c[i] = 'B';
      |                                   ~~^~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 157 ms 7104 KB Output is correct
3 Correct 153 ms 7544 KB Output is correct
4 Correct 143 ms 7236 KB Output is correct
5 Correct 147 ms 9056 KB Output is correct
6 Correct 148 ms 6356 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 157 ms 7104 KB Output is correct
3 Correct 153 ms 7544 KB Output is correct
4 Correct 143 ms 7236 KB Output is correct
5 Correct 147 ms 9056 KB Output is correct
6 Correct 148 ms 6356 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 157 ms 7104 KB Output is correct
3 Correct 153 ms 7544 KB Output is correct
4 Correct 143 ms 7236 KB Output is correct
5 Correct 147 ms 9056 KB Output is correct
6 Correct 148 ms 6356 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -