Submission #75283

#	Time	Username	Problem	Language	Result	Execution time	Memory
75283		Yehezkiel	Match (CEOI16_match)	C++11	100 / 100	97 ms	13836 KiB

match

#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 cout                if (false) cout

#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) {
        cout<<"sizenya "<<tumpuk.size()<<endl;
        hashValue = hashValue + convert[newChar - 'a'] * multiplier[tumpuk.size()];
        tumpuk.push(newChar);
        cout<<"done"<<endl;
    }

    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++) {
        cout<<"lagi loop ke "<<i<<endl;
        sebelum[i] = characters.generateHash();
        if(characters.empty()) {
            cout<<"masuk sini"<<endl;
            characters.push(input[i]);
        } else 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;
    cout<<"posisi "<<l<<" "<<r<<endl;
    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();

    cout<<"generating hash success"<<endl;
    if (possible()) {
        makeAns();
        printf("%s\n",ans);
    } else {
        printf("-1\n");
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63