oj.uz

Submission #937720

# Submission time Handle Problem Language Result Execution time Memory
937720 2024-03-04T11:55:05 Z zwezdinv Modern Machine (JOI23_ho_t5) C++17
26 / 100
 3000 ms 9200 KB 
#include <bits/stdc++.h>

std::string process(std::string c, int k) {
        c[k] = 'R';
        std::vector<int> lr, rl;
        for (int i = k - 1; i >= 0; --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 (rl.empty()) {
                for (int i = k; i < c.size(); ++i) c[i] = 'B';
        } else if (lr.size() >= rl.size()) {
                int k = rl.size();
                int pos = lr[k - 1];
                for (int i = pos; i < c.size(); ++i) c[i] = 'B';
        } else {
                int k = lr.size();
                int pos = rl[k];
                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:13:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |                 for (int i = k; i < c.size(); ++i) c[i] = 'B';
      |                                 ~~^~~~~~~~~~
Main.cpp:17:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |                 for (int i = pos; i < c.size(); ++i) c[i] = 'B';
      |                                   ~~^~~~~~~~~~

Subtask #1
3.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 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
12.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 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 84 ms 528 KB Output is correct
11 Correct 36 ms 348 KB Output is correct
12 Correct 84 ms 552 KB Output is correct
13 Correct 151 ms 528 KB Output is correct
14 Correct 119 ms 540 KB Output is correct

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 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 84 ms 528 KB Output is correct
11 Correct 36 ms 348 KB Output is correct
12 Correct 84 ms 552 KB Output is correct
13 Correct 151 ms 528 KB Output is correct
14 Correct 119 ms 540 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Execution timed out 3076 ms 2344 KB Time limit exceeded
19 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 177 ms 7164 KB Output is correct
3 Correct 166 ms 7536 KB Output is correct
4 Correct 132 ms 7084 KB Output is correct
5 Correct 157 ms 9200 KB Output is correct
6 Correct 146 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 177 ms 7164 KB Output is correct
3 Correct 166 ms 7536 KB Output is correct
4 Correct 132 ms 7084 KB Output is correct
5 Correct 157 ms 9200 KB Output is correct
6 Correct 146 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 145 ms 348 KB Output is correct
11 Execution timed out 3013 ms 3736 KB Time limit exceeded
12 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 177 ms 7164 KB Output is correct
3 Correct 166 ms 7536 KB Output is correct
4 Correct 132 ms 7084 KB Output is correct
5 Correct 157 ms 9200 KB Output is correct
6 Correct 146 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 344 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 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 84 ms 528 KB Output is correct
11 Correct 36 ms 348 KB Output is correct
12 Correct 84 ms 552 KB Output is correct
13 Correct 151 ms 528 KB Output is correct
14 Correct 119 ms 540 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Execution timed out 3076 ms 2344 KB Time limit exceeded
19 Halted 0 ms 0 KB -