oj.uz

Submission #174294

# Submission time Handle Problem Language Result Execution time Memory
174294 2020-01-06T10:44:12 Z Ruxandra985 Match (CEOI16_match) C++14
10 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>

using namespace std;
set <int> h[30] ;
priority_queue <int> small;
set <int> :: iterator it , it2;
int s[100010];
char sol[100010];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , ok , ed;
    char c;
    c=fgetc(fin);
    n = 0;
    while ( 'a' <= c && c <= 'z' ){
        s[++n] = c-'a';
        h[c-'a'].insert(n); /// pozitii
        c=fgetc(fin);
    }
    ok = 1;
    small.push(-n-1);
    for ( i = 1 ; i <= n ; i++ ){
        if (sol[i] == 0){
            /// nu ai pus inca
            sol[i] = '(';
            while (!small.empty() && -small.top() < i)
                small.pop();
            /// small.top() = cea mai mica poz a unei paranteze inchise

            it = h[s[i]].lower_bound(-small.top());
            it--;
            ed = *it;

            if (ed <= i){
                ok = -1;
                break;
            }
            else {

                /// sfarsitul de acum trebuie sa fie mai mic decat sfarsiturile
                /// mai mari decat i

                h[s[i]].erase(it);
                sol[ed] = ')';
                small.push(-ed);

            }
        }

    }
    if (ok == -1){
        fprintf (fout,"%d",ok);
    }
    else {
        for (i=1;i<=n;i++)
            fputc(sol[i],fout);
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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