# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
647847 | raresmihai | parentrises (BOI18_parentrises) | C++17 | 1 ms | 340 KiB |
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);
}
good = true;
if ( good ) {
for ( pos = 0; pos < n; pos++ ) {
fputc(ans[pos], stdout);
}
printf("\n");
} else {
printf("impossible\n");
}
}
}
return 0;
}
Compilation message (stderr)
# | 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... |