This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#define MAXL 1000000
using namespace std;
struct paranthesis{
bool type;
int pos;
};
int posOfOpen[MAXL], posOfOpenSize;
paranthesis bad[MAXL + 2];
int badSize;
char ans[MAXL];
int goodOpen[MAXL], goodOpenSize;
int goodClosed[MAXL], goodClosedSize;
int bs1(int val) {
int st, dr, mij;
st = -1;
dr = goodClosedSize - 1;
while ( dr - st > 1 ) {
mij = (dr + st) / 2;
if ( goodClosed[mij] < val )
st = mij;
else
dr = mij;
}
return dr;
}
int bs2(int val) {
int st, dr, mij;
st = 0;
dr = goodOpenSize;
while ( dr - st > 1 ) {
mij = (st + dr) / 2;
if ( goodOpen[mij] > val )
dr = mij;
else
st = mij;
}
return st;
}
int main() {
int c, t, i, pos, lastPosOpen, lastPosClosed, n;
char ch;
bool good;
scanf("%d", &c);
if ( c == 1 ) {
scanf("%d ", &t);
while ( t-- ) {
posOfOpenSize = goodClosedSize = goodOpenSize = 0;
badSize = 1;
ch = fgetc(stdin);
i = 0;
n = 0;
while ( ch == '(' || ch == ')' ) {
ans[i] = 'R';
if ( ch == '(' ) {
posOfOpen[posOfOpenSize] = i;
posOfOpenSize++;
} else {
if ( posOfOpenSize ) {
posOfOpenSize--;
goodOpen[goodOpenSize] = posOfOpen[posOfOpenSize];
goodOpenSize++;
goodClosed[goodClosedSize] = i;
goodClosedSize++;
ans[i] = ans[posOfOpen[posOfOpenSize]] = 'R';
} else {
bad[badSize].pos = i;
bad[badSize].type = true;
badSize++;
}
}
i++;
n++;
ch = fgetc(stdin);
}
posOfOpenSize--;
while ( posOfOpenSize >= 0 ) {
bad[badSize].pos = posOfOpen[posOfOpenSize];
bad[badSize].type = false;
badSize++;
posOfOpenSize--;
}
good = true;
bad[badSize].pos = i + 1;
bad[0].pos = -1;
badSize--;
lastPosOpen = i;
lastPosClosed = 0;
sort(goodOpen, goodOpen + goodOpenSize);
while ( badSize && good ) {
// ans[bad[badSize].pos] = 'B';
if ( !bad[badSize].type ) {
pos = goodClosed[bs1(max(lastPosClosed, bad[badSize].pos) + 1)];
if ( pos > max(lastPosClosed, bad[badSize].pos) ) {
//ans[pos] = 'G';
lastPosClosed = pos;
} else {
good = false;
}
} else {
pos = goodOpen[bs2(min(bad[badSize].pos, lastPosOpen) - 1)];
if ( pos < min(bad[badSize].pos, lastPosOpen) ) {
// ans[pos] = 'G';
lastPosOpen = pos;
} else {
good = false;
}
}
badSize--;
}
if ( good ) {
for ( pos = 0; pos < n; pos++ ) {
fputc(ans[pos], stdout);
}
printf("\n");
} else {
printf("impossible\n");
}
}
}
return 0;
}
Compilation message (stderr)
parentrises.cpp: In function 'int main()':
parentrises.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &c);
| ~~~~~^~~~~~~~~~
parentrises.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d ", &t);
| ~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |