oj.uz

Submission #750968

# Submission time Handle Problem Language Result Execution time Memory
750968 2023-05-30T17:04:30 Z joelgun14 Crossing (JOI21_crossing) C++17
26 / 100
 7000 ms 2036 KB 
// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
string operate(string a, string b) {
    for(int it = 0; it < a.size(); ++it) {
        if(a[it] == b[it])
            continue;
        bool j = 0, o = 0, i = 0;
        if(a[it] == 'J')
            j = 1;
        else if(a[it] == 'O')
            o = 1;
        else
            i = 1;
        if(b[it] == 'J')
            j = 1;
        else if(b[it] == 'O')
            o = 1;
        else
            i = 1;
        if(!j)
            a[it] = 'J';
        else if(!o)
            a[it] = 'O';
        else
            a[it] = 'I';
    }
    return a;
}
// buat bit 27 state 1 nya implicit disimpan di segment bawahnya
// remove segment bawahnya per segment gtu
// nanti cnt cari mutually exclusive segment
int cnt[3][3][3][3];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int n;
    cin >> n;
    // coba cek tiap possibility pengambilan
    // max pengambilan cmn 3?
    string a[3];
    cin >> a[0] >> a[1] >> a[2];
    int q;
    cin >> q;
    string init;
    cin >> init;
    bool ans = 0;
    for(int i = 0; i < 3; ++i) {
        string tmp = a[i];
        for(int j = 0; j < 3; ++j) {
            // lakuin operasi antara a[i] dan a[j];
            tmp = operate(tmp, a[j]);
            for(int k = 0; k < 3; ++k) {
                tmp = operate(tmp, a[k]);
                if(tmp == init)
                    ans = 1;
            }
        }
    }
    if(ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    // coba permutasi size 1, 2, 3
    // given same sequence tp resultnya beda -> pasti gabisa -> O(81Q) -> 1.6e7
    // klo misal ga ada yg beda, berarti max ada 27 aja
    // klo 27, nanti cek O(27^2*Q) -> 1.4e8
    // total O(81Q)
    while(q--) {
        int l, r;
        char x;
        cin >> l >> r >> x;
        for(int i = l - 1; i <= r - 1; ++i)
            init[i] = x;
        bool ans = 0;
        for(int i = 0; i < 3; ++i) {
            string tmp = a[i];
            for(int j = 0; j < 3; ++j) {
                // lakuin operasi antara a[i] dan a[j];,
                tmp = operate(tmp, a[j]);
                for(int k = 0; k < 3; ++k) {
                    tmp = operate(tmp, a[k]);
                    if(tmp == init)
                        ans = 1;
                }
            }
        }
        if(ans)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'std::string operate(std::string, std::string)':
Main.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int it = 0; it < a.size(); ++it) {
      |                     ~~~^~~~~~~~~~
Main.cpp:27:28: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   27 |         bool j = 0, o = 0, i = 0;
      |                            ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 908 KB Output is correct
2 Correct 1236 ms 968 KB Output is correct
3 Correct 1248 ms 948 KB Output is correct
4 Correct 1182 ms 988 KB Output is correct
5 Correct 1149 ms 988 KB Output is correct
6 Correct 1124 ms 912 KB Output is correct
7 Correct 1115 ms 836 KB Output is correct
8 Correct 1215 ms 1056 KB Output is correct
9 Correct 1270 ms 1040 KB Output is correct
10 Correct 1272 ms 872 KB Output is correct
11 Correct 1231 ms 868 KB Output is correct
12 Correct 1210 ms 932 KB Output is correct
13 Correct 1220 ms 944 KB Output is correct
14 Correct 1220 ms 1016 KB Output is correct
15 Correct 1175 ms 816 KB Output is correct
16 Correct 1228 ms 1116 KB Output is correct
17 Correct 1290 ms 940 KB Output is correct
18 Correct 1227 ms 908 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 908 KB Output is correct
2 Correct 1236 ms 968 KB Output is correct
3 Correct 1248 ms 948 KB Output is correct
4 Correct 1182 ms 988 KB Output is correct
5 Correct 1149 ms 988 KB Output is correct
6 Correct 1124 ms 912 KB Output is correct
7 Correct 1115 ms 836 KB Output is correct
8 Correct 1215 ms 1056 KB Output is correct
9 Correct 1270 ms 1040 KB Output is correct
10 Correct 1272 ms 872 KB Output is correct
11 Correct 1231 ms 868 KB Output is correct
12 Correct 1210 ms 932 KB Output is correct
13 Correct 1220 ms 944 KB Output is correct
14 Correct 1220 ms 1016 KB Output is correct
15 Correct 1175 ms 816 KB Output is correct
16 Correct 1228 ms 1116 KB Output is correct
17 Correct 1290 ms 940 KB Output is correct
18 Correct 1227 ms 908 KB Output is correct
19 Execution timed out 7096 ms 2036 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 908 KB Output is correct
2 Correct 1236 ms 968 KB Output is correct
3 Correct 1248 ms 948 KB Output is correct
4 Correct 1182 ms 988 KB Output is correct
5 Correct 1149 ms 988 KB Output is correct
6 Correct 1124 ms 912 KB Output is correct
7 Correct 1115 ms 836 KB Output is correct
8 Correct 1215 ms 1056 KB Output is correct
9 Correct 1270 ms 1040 KB Output is correct
10 Correct 1272 ms 872 KB Output is correct
11 Correct 1231 ms 868 KB Output is correct
12 Correct 1210 ms 932 KB Output is correct
13 Correct 1220 ms 944 KB Output is correct
14 Correct 1220 ms 1016 KB Output is correct
15 Correct 1175 ms 816 KB Output is correct
16 Correct 1228 ms 1116 KB Output is correct
17 Correct 1290 ms 940 KB Output is correct
18 Correct 1227 ms 908 KB Output is correct
19 Correct 2512 ms 888 KB Output is correct
20 Correct 2748 ms 920 KB Output is correct
21 Correct 1770 ms 1100 KB Output is correct
22 Correct 1400 ms 936 KB Output is correct
23 Correct 2054 ms 952 KB Output is correct
24 Correct 1829 ms 856 KB Output is correct
25 Correct 2216 ms 1068 KB Output is correct
26 Correct 1503 ms 872 KB Output is correct
27 Correct 2281 ms 972 KB Output is correct
28 Correct 1880 ms 848 KB Output is correct
29 Correct 2185 ms 852 KB Output is correct
30 Correct 1485 ms 824 KB Output is correct
31 Correct 2810 ms 1012 KB Output is correct
32 Correct 2451 ms 812 KB Output is correct
33 Correct 2678 ms 992 KB Output is correct
34 Correct 1857 ms 960 KB Output is correct
35 Correct 2613 ms 972 KB Output is correct
36 Correct 2681 ms 968 KB Output is correct
37 Correct 2723 ms 1204 KB Output is correct
38 Correct 2503 ms 1056 KB Output is correct
39 Correct 2708 ms 1052 KB Output is correct
40 Correct 2684 ms 1000 KB Output is correct
41 Correct 2676 ms 1104 KB Output is correct
42 Correct 2774 ms 856 KB Output is correct
43 Correct 2159 ms 880 KB Output is correct
44 Correct 2684 ms 936 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 908 KB Output is correct
2 Correct 1236 ms 968 KB Output is correct
3 Correct 1248 ms 948 KB Output is correct
4 Correct 1182 ms 988 KB Output is correct
5 Correct 1149 ms 988 KB Output is correct
6 Correct 1124 ms 912 KB Output is correct
7 Correct 1115 ms 836 KB Output is correct
8 Correct 1215 ms 1056 KB Output is correct
9 Correct 1270 ms 1040 KB Output is correct
10 Correct 1272 ms 872 KB Output is correct
11 Correct 1231 ms 868 KB Output is correct
12 Correct 1210 ms 932 KB Output is correct
13 Correct 1220 ms 944 KB Output is correct
14 Correct 1220 ms 1016 KB Output is correct
15 Correct 1175 ms 816 KB Output is correct
16 Correct 1228 ms 1116 KB Output is correct
17 Correct 1290 ms 940 KB Output is correct
18 Correct 1227 ms 908 KB Output is correct
19 Execution timed out 7096 ms 2036 KB Time limit exceeded
20 Halted 0 ms 0 KB -