oj.uz

Submission #91024

# Submission time Handle Problem Language Result Execution time Memory
91024 2018-12-25T15:56:40 Z choikiwon parentrises (BOI18_parentrises) C++17
0 / 100
 2 ms 644 KB 
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int MN = 1000010;

struct BIT {
    int Z;
    vector<int> tree, lazy;
    void init(int Z_) {
        Z = Z_;
        tree = vector<int>(4 * Z, 0);
        lazy = vector<int>(4 * Z, 0);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n] += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1] += lazy[n];
            lazy[2*n + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, int d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 1e9;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return min(L, R);
    }
    void upd(int a, int b, int d) { upd(a, b, d, 0, Z - 1, 1); }
    int quer(int a, int b) { return quer(a, b, 0, Z - 1, 1); }
} bit1, bit2;

string S, ans;
set<int> R[2], B[2], G[2];

void main2() {
    cin >> S;

    ans.clear();
    ans.resize(S.size());
    bit1.init(S.size());
    bit2.init(S.size());
    for(int i = 0; i < 2; i++) {
        R[i].clear();
        B[i].clear();
        G[i].clear();
    }
    int rg = 0;
    int bg = 0;
    for(int i = 0; i < S.size(); i++) {
        if(S[i] == '(') {
            rg++;
            R[1].insert(i);
            bit1.upd(i, (int)S.size() - 1, 1);
        }
        else {
            if(rg) {
                rg--;
                R[0].insert(i);
                bit1.upd(i, (int)S.size() - 1, -1);
            }
            else if(bg) {
                bg--;
                B[0].insert(i);
                bit2.upd(i, (int)S.size() - 1, -1);
            }
            else {
                B[0].insert(i);
                bit2.upd(i, (int)S.size() - 1, -1);
                if(R[1].size()) {
                    int t = *R[1].begin();
                    R[1].erase(t);
                    G[1].insert(t);
                    bit1.upd(t, (int)S.size() - 1, 1);
                    bit2.upd(t, (int)S.size() - 1, 1);
                }
                else {
                    cout << "impossible\n";
                    return;
                }
            }
        }
    }
    while(rg) {
        while(R[1].size()) {
            int t = *R[1].begin();
            R[1].erase(t);
            if(bit1.quer(t, (int)S.size() - 1)) {
                rg--;
                bit1.upd(t, (int)S.size() - 1, -1);

                B[1].insert(t);
                bg++;
                bit2.upd(t, (int)S.size() - 1, 1);
                break;
            }
            else {
                ans[t] = 'R';
            }
        }
    }
    while(bg) {
        if(R[0].size()) {
            int t = *R[0].rbegin();
            R[0].erase(t);
            G[0].insert(t);
            bg--;
        }
        else {
            cout << "impossible\n";
            return;
        }
    }

    for(int i = 0; i < 2; i++) {
        for(auto it = R[i].begin(); it != R[i].end(); it++) {
            ans[*it] = 'R';
        }
        for(auto it = B[i].begin(); it != B[i].end(); it++) {
            ans[*it] = 'B';
        }
        for(auto it = G[i].begin(); it != G[i].end(); it++) {
            ans[*it] = 'G';
        }
    }

    rg = bg = 0;
    for(int i = 0; i < ans.size(); i++) {
        if(S[i] == '(') {
            if(ans[i] != 'B') rg++;
            if(ans[i] != 'R') bg++;
        }
        else {
            if(ans[i] != 'B') rg--;
            if(ans[i] != 'R') bg--;
        }
        if(rg < 0 || bg < 0) {
            cout << "impossible\n";
            return;
        }
    }

    cout << ans << endl;
}

void main3() {

}

int P, TC;
int main() {
    std::ios::sync_with_stdio(false);

    cin >> P >> TC;
    if(P == 1) {
        while(TC--) main2();
    }
    if(P == 2) {
        while(TC--) main3();
    }
}

Compilation message

parentrises.cpp: In function 'void main2()':
parentrises.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~
parentrises.cpp:145:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++) {
                    ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Incorrect 2 ms 644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 644 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 644 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 644 KB Unexpected end of file - int32 expected