oj.uz

Submission #480123

# Submission time Handle Problem Language Result Execution time Memory
480123 2021-10-14T18:14:32 Z hidden1 parentrises (BOI18_parentrises) C++14
50 / 100
 164 ms 7216 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}
 
const int MAX_L = 1e5 + 10;

string s;

void solve1() {
    int t;
    cin >> t;
    while(t --) {
        cin >> s;
        string ans = "";
        vector<int> blue, red;
        int balance = 0;
        bool good = true;
        for(int i = 0; i < s.size(); i ++) {
            ans += '?';
        }
        for(int i = 0; i < s.size(); i ++) {
            auto it = s[i];
            if(it == '(') {
                blue.push_back(i);
                red.push_back(i);
            } else {
                if(blue.empty()) {
                    if(red.empty()) {
                        good = false;
                        break;
                    } else {
                        ans[red.back()] = 'G';
                        ans[i] = 'R';
                        red.pop_back();
                    }
                } else {
                    ans[blue.back()] = 'B';
                    ans[i] = 'B';                    
                    blue.pop_back();
                }
            }
        }
        vector<int> notUsed;
        for(int i = 0; i < s.size(); i ++) {
            auto it = s[i];
            if(ans[i] == '?') {
                notUsed.push_back(i);
            } else if(it == ')' && !notUsed.empty()) {
                if(ans[i] == 'R') {
                    ans[notUsed.back()] = 'B';
                    notUsed.pop_back();
                    ans[i] = 'G';
                } else if(ans[i] == 'B') {
                    ans[notUsed.back()] = 'R';
                    notUsed.pop_back();
                    ans[i] = 'G';                    
                }
            }
        }
        if(good && notUsed.empty()) {
            cout << ans << endl;
        } else {
            cout << "impossible" << endl;            
        }
    }
}

signed main() {
    // ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int t;
    cin >> t;
    if(t == 1) {
        solve1();
    }

    return 0;
}

Compilation message

parentrises.cpp: In function 'void solve1()':
parentrises.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i = 0; i < s.size(); i ++) {
      |                        ~~^~~~~~~~~~
parentrises.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i = 0; i < s.size(); i ++) {
      |                        ~~^~~~~~~~~~
parentrises.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i = 0; i < s.size(); i ++) {
      |                        ~~^~~~~~~~~~
parentrises.cpp:34:13: warning: unused variable 'balance' [-Wunused-variable]
   34 |         int balance = 0;
      |             ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 21 ms 456 KB Output is correct
17 Correct 6 ms 1080 KB Output is correct
18 Correct 5 ms 580 KB Output is correct
19 Correct 6 ms 816 KB Output is correct
20 Correct 6 ms 1036 KB Output is correct
21 Correct 164 ms 1952 KB Output is correct
22 Correct 59 ms 7216 KB Output is correct
23 Correct 44 ms 2932 KB Output is correct
24 Correct 50 ms 4040 KB Output is correct
25 Correct 55 ms 7208 KB Output is correct

Subtask #5
0 / 6.0

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

Subtask #6
0 / 16.0

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

Subtask #7
0 / 28.0

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