Submission #95296

#	Time	Username	Problem	Language	Result	Execution time	Memory
95296		pranjalssh	Match (CEOI16_match)	C++14	10 / 100	2 ms	504 KiB

match

/*
	Idea: Match S[1] with last occurence of S[1] and recurse in two remaining rangse.
*/
#include <bits/stdc++.h>
using namespace std;

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    string s; cin >> s;
    int n = sz(s);
    vector<vi> last(n, vi(26, -1));
    FOR (i, 0, n - 1) {
    	if (i) FOR (j, 0, 25) last[i][j] = last[i-1][j];
    	last[i][s[i]-'a'] = i;
    }
    bool good = true;
    function<void(int,int)>f = [&](int l, int r) {
    	if (l > r) return;
    	if ((r-l+1)%2) {good = false; return;}

    	int pos = last[r][s[l]-'a'];
    	if (pos < l) {good = false; return;}
    	s[l] = '('; s[pos] = ')';
    	f(l+1, pos-1);
    	f(pos+1, r);
    };
    f(0, n-1);
    if (good) cout << s << "\n";
    else cout << "-1\n";
    
    return 0;
}

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