제출 #174294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
174294		Ruxandra985	괄호 문자열 (CEOI16_match)	C++14	10 / 100	2 ms	380 KiB

match

#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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63