| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 75284 |
2018-09-09T05:50:20 Z |
Yehezkiel |
Match (CEOI16_match) |
C++11 |
|
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");
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
