oj.uz

Submission #64216

# Submission time Handle Problem Language Result Execution time Memory
64216 2018-08-03T13:51:37 Z Talant parentrises (BOI18_parentrises) C++17
0 / 100
 3 ms 560 KB 
#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

int t,k,n;
int b[N],blc[N];
char ans[N];

string a;

main () {
      cin >> k;
      cin >> t;

      while (t --) {
            int flag = 0,last = 0;
            cin >> a;

            n = a.size();
            int lst = n - 1;

            for (int i = 0; i <= n; i ++) b[i] = blc[i] = 0,ans[i] = '0';

            for (int i = 0; i < a.size(); i ++) {
                  if (i > 0) b[i] = b[i - 1];
                  b[i] = max(0,b[i]);

                  if (a[i] == '(') b[i] ++;
                  else b[i] --;
                  if (b[i] < 0) ans[i] = 'B';
            }
            for (int i = n - 1; i >= 0; i --) {
                  if (i < n - 1) blc[i] = blc[i + 1];
                  blc[i] = max(0,blc[i]);

                  if (a[i] == ')') blc[i] ++;
                  else blc[i] --;
                  if (blc[i] < 0) ans[i] = 'B';
            }
            for (int i = 0; i < n; i ++) {
                  if (ans[i] == 'B') {
                        if (a[i] == ')') {
                              int f = 0;
                              for (int j = last; j < i; j ++) {
                                    if (ans[j] == '0' && a[j] == '('){ ans[j] = 'G',f = 1;last = j;break;}
                              }
                              if (!f) {
                                    puts("impossible");
                                    flag = 1;
                                    break;
                              }
                        }
                        else {
                              int f = 0;
                              for (int j = lst; j > i; j --) {
                                    if (ans[j] == '0' && a[j] == ')') { ans[j] = 'G',f = 1;lst = j;break;
                                    }
                              }
                              if (!f) {
                                    puts("impossible");
                                    flag = 1;
                                    break;
                              }
                        }
                  }
            }
            if (flag) continue;

            for (int i = 0; i < n; i ++) {
                  if (ans[i] == '0') ans[i] = 'R';
                  cout << ans[i];
            }

            cout << endl;
      }
}

Compilation message

parentrises.cpp:23:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
parentrises.cpp: In function 'int main()':
parentrises.cpp:36:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < a.size(); i ++) {
                             ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 560 KB Expected integer, but "impossible" found

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 560 KB Expected integer, but "impossible" found

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 560 KB Expected integer, but "impossible" found