Submission #64220

#	Time	Username	Problem	Language	Result	Execution time	Memory
64220		Talant	parentrises (BOI18_parentrises)	C++17	50 / 100	190 ms	11520 KiB

parentrises

#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)2e6 + 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,lst = 0;
            cin >> a;

            n = a.size();

            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 + 1;break;}
                              }
                              if (!f) {
                                    puts("impossible");
                                    flag = 1;
                                    break;
                              }
                        }
                        else {
                              int f = 0;
                              for (int j = max(i,lst); j < n; j ++) {
                                    if (ans[j] == '0' && a[j] == ')') { ans[j] = 'G',f = 1;lst = j + 1;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 (stderr)

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:35:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < a.size(); i ++) {
                             ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28