oj.uz

Submission #494305

# Submission time Handle Problem Language Result Execution time Memory
494305 2021-12-15T03:59:03 Z SirCovidThe19th parentrises (BOI18_parentrises) C++17
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define add(a, b) a = (a + b) % md

const int md = 1e9 + 7;

void solve1(){
    int n; string A; cin >> A; n = A.size();

    int sm = 0, R[n], G[n], B[n], maxRem[n], maxAdd[n]; 
    FOR(i, 0, n) R[i] = 1, G[i] = B[i] = 0, maxRem[i] = 1e9, maxAdd[i] = 1e9;
    queue<int> close;
    FOR(i, 0, n){
        sm += (A[i] == '(' ? 1 : -1);
        if (A[i] == ')'){ //greedily remove ) from frnot
            close.push(i); 
            if (sm < 0){
                int pos = close.front(); close.pop();
                R[pos] = 0; B[pos] = 1; sm = 0;
            }
            maxRem[i] = sm;
        }
    }
    for (int i = n - 2; ~i; i--) maxRem[i] = min(maxRem[i], maxRem[i + 1]);

    if (sm > 0){ //greedily remove ( from front
        int curRem = 0;
        FOR(i, 0, n) if (A[i] == '(' and curRem < maxRem[i]) 
            R[i] = 0, B[i] = 1, curRem++;
        if (curRem != sm){ cout<<"Impossible"<<endl; return; }
    }
    sm = 0; queue<int> open;
    FOR(i, 0, n){
        if (R[i]){
            if (A[i] == '(') open.push(i);
            continue;
        }
        sm += (A[i] == '(' ? 1 : -1);
        if (sm < 0){ //greedily add (
            if (open.empty()){ cout<<"Impossible"<<endl; return; }
            int pos = open.front(); open.pop();
            R[pos] = 0; G[pos] = 1; sm = 0;
        }
        if (A[i] == ')') maxAdd[i] = i;
    }
    for (int i = n - 2; ~i; i--) maxAdd[i] = min(maxAdd[i], maxAdd[i + 1]);
    if (sm > 0){ //greedily add ) to end
        int curAdd = 0;
        for (int i = n - 1; ~i; i--) if (A[i] == ')' and R[i] and curAdd < maxAdd[i] and curAdd < sm)
            R[i] = 0, G[i] = 1, curAdd++;
        if (curAdd != sm){ cout<<"Impossible"<<endl; }
    }
    FOR(i, 0, n) cout<<(R[i] ? 'R' : G[i] ? 'G' : 'B');
    cout<<endl;
}
void solve2(){
    
}

int main(){
    int type, tc; cin >> type >> tc;
    while (tc--) type == 1 ? solve1() : solve2();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 6.0

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

Subtask #6
0 / 16.0

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

Subtask #7
0 / 28.0

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