oj.uz

답안 #75284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75284 2018-09-09T05:50:20 Z Yehezkiel 괄호 문자열 (CEOI16_match) C++11
100 / 100
 106 ms 13088 KB 
#include <bits/stdc++.h>
using namespace std;

#define LL 					long long
#define DB					double
#define ULL 				unsigned long long
#define PII 				pair<int,int>
#define ALL(x)			 	(x).begin(),(x).end()
#define SZ(x)				(int)(x).size()

#define fi 					first
#define se 					second
#define psb 				push_back
#define ppb 				pop_back
#define endln 				printf("\n")
#define mp                  make_pair

#define SETMIN(x)			memset((x), -1, sizeof (x))
#define SETNUL(x)			memset((x),  0, sizeof (x))
#define gc					getchar_unlocked

#ifndef getchar_unlocked
#define getchar_unlocked 	getchar
#endif

const int inf = 1e9 + 5;
const LL infll = 1e18+5;
const int mod = 1e9 + 7;

template <typename T>
void gi(T &ret) {
	ret = 0; char inp = gc(); bool isNeg = 0;
	while (inp < '0' || inp > '9') { 
		if (inp == '-') isNeg = 1; 
		inp = gc();
	}
	while ('0' <= inp && inp <= '9') {
		ret = (ret << 3) + (ret << 1) + (inp - '0');
		inp = gc();
	}
	if (isNeg) ret = -ret;
}

const LL mods = 1000000007LL;
struct M {
    LL x;
    M () {
        x=0;
    }
    
    M (LL angka) {
        if (angka >= mods || angka <= -mods) {
            angka %= mods;
        }
        if ( angka < 0 ) {
            angka += mods;
        }

        x = angka;
    }

    M operator + (const M &other) const {
        return M(x + other.x);
    }

    M operator - (const M &other) const {
        return M(x - other.x);
    }

    M operator * (const M &other) const {
        return M(x * other.x);
    }

    M operator - () const {
        return M(-x);
    }
};

const int totalHash=2;
struct hashScore {
    M val[totalHash];

    hashScore () {
        for (int i = 0; i < totalHash; i++) {
            val[i] = 0;
        }
    }

    void randomAssign () {
        for (int i = 0; i < totalHash ; i++) {
            val[i] = rand();
        }
    }

    hashScore operator + (const hashScore &other) const {
        hashScore ret;
        for (int i = 0; i < totalHash; i++) {
            ret.val[i] = val[i] + other.val[i]; 
        }
        return ret;
    }

    hashScore operator * (const hashScore &other) const {
        hashScore ret;
        for (int i = 0; i < totalHash; i++) {
            ret.val[i] = val[i] * other.val[i]; 
        }
        return ret;
    }

    hashScore operator - (const hashScore &other) const {
        hashScore ret;
        for (int i = 0; i < totalHash; i++) {
            ret.val[i] = val[i] - other.val[i]; 
        }
        return ret;
    }

    bool operator < (const hashScore &other) const {
        for (int i = 0; i < totalHash; i++) {
            if (val[i].x != other.val[i].x) {
                return val[i].x < other.val[i].x;
            }
        }
        return false;
    }
};

const int MAXN = 100000;
const int TOTALCHARACTER = 26;
int n;
string input;
hashScore multiplier[MAXN+5];
hashScore convert[TOTALCHARACTER];
void generateHash () {
    for (int i = 0; i < n; i++) {
        multiplier[i].randomAssign();
    }

    for (int i = 0; i < TOTALCHARACTER; i++) {
        convert[i]. randomAssign();
    }
}

struct modifiedStack {
    stack <char> tumpuk;
    hashScore hashValue;

    char top () {
        return tumpuk.top();
    }

    void push (char newChar) {
        hashValue = hashValue + convert[newChar - 'a'] * multiplier[tumpuk.size()];
        tumpuk.push(newChar);
    }

    void pop () {
        char temp = top();
        tumpuk.pop();
        hashValue = hashValue - convert[temp - 'a'] * multiplier[tumpuk.size()];
    }

    bool empty () {
        return tumpuk.empty();
    }

    hashScore generateHash () {
        return hashValue;
    }
};

hashScore sebelum[MAXN + 5];
hashScore sesudah[MAXN + 5];
set < pair < hashScore, int > > daftar[TOTALCHARACTER];

bool possible(){
    modifiedStack characters;
    for (int i = 0; i < n ; i++) {
        sebelum[i] = characters.generateHash();
        if (!characters.empty() && characters.top() == input[i]) {
            characters.pop();
        } else {
            characters.push(input[i]);
        }
        sesudah[i] = characters.generateHash();
        daftar[input[i] - 'a'].insert(mp(sesudah[i], i));
    }
    return characters.empty();
}

char ans[MAXN + 5];
void makeAns (int l,int r) {
    if(l > r)
        return;
    int jodoh = prev(daftar[input[l] - 'a'].upper_bound(mp(sebelum[l],r)))->se;

    ans[l] = '(';
    ans[jodoh] = ')';

    makeAns(l + 1, jodoh - 1);
    makeAns(jodoh + 1, r);
}
void makeAns () {
    ans[n] = '\0';
    makeAns(0, n-1);
}
int main() {
    cin>>input;
    n = input.length();
    generateHash();

    if (possible()) {
        makeAns();
        printf("%s\n",ans);
    } else {
        printf("-1\n");
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5108 KB Output is correct
3 Correct 5 ms 5108 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5108 KB Output is correct
3 Correct 5 ms 5108 KB Output is correct
4 Correct 6 ms 5200 KB Output is correct
5 Correct 6 ms 5256 KB Output is correct
6 Correct 7 ms 5276 KB Output is correct
7 Correct 6 ms 5280 KB Output is correct

Subtask #3
63.0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5108 KB Output is correct
3 Correct 5 ms 5108 KB Output is correct
4 Correct 6 ms 5200 KB Output is correct
5 Correct 6 ms 5256 KB Output is correct
6 Correct 7 ms 5276 KB Output is correct
7 Correct 6 ms 5280 KB Output is correct
8 Correct 9 ms 5680 KB Output is correct
9 Correct 9 ms 5680 KB Output is correct
10 Correct 9 ms 5824 KB Output is correct
11 Correct 10 ms 6012 KB Output is correct
12 Correct 48 ms 9872 KB Output is correct
13 Correct 55 ms 10384 KB Output is correct
14 Correct 57 ms 10912 KB Output is correct
15 Correct 55 ms 12068 KB Output is correct
16 Correct 55 ms 12068 KB Output is correct
17 Correct 84 ms 12448 KB Output is correct
18 Correct 70 ms 12448 KB Output is correct
19 Correct 104 ms 12492 KB Output is correct
20 Correct 49 ms 12492 KB Output is correct
21 Correct 106 ms 13088 KB Output is correct