QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460760#5534. Matchfryan0 21ms6716kbC++202.1kb2024-07-02 08:08:182024-07-02 08:08:18

Judging History

你现在查看的是最新测评结果

  • [2024-07-02 08:08:18]
  • 评测
  • 测评结果:0
  • 用时:21ms
  • 内存:6716kb
  • [2024-07-02 08:08:18]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 1e5;
const int mod = 998244353;
const int p = 53;

int ksm(int a, int b=mod-2) {
	int res=1, aux=a;
	for (int i=1; i<=b; i*=2) {
		if (b&i) res = res*aux%mod;
		aux = aux*aux%mod;
	}
	return res;
}

int n, s[mxn], pw[2*mxn], ip[2*mxn], hv[mxn+2];
vector<int> stk;
map<array<int,2>,vector<int>> ep;

vector<int> solve(int l, int r) {
	if (l+1 == r) {
		assert(s[l] == s[r]);
		return {0,1};
	}
	int f = s[l];
	int h = hv[l];
	array<int,2> k = {f,h};
	auto it = upper_bound(all(ep[k]),r);
	--it;
	int rb = *it;
	vector<int> res = {0};
	if (l+1 < rb) {
		vector<int> r1 = solve(l+1,rb-1);
		for (auto i : r1) {
			res.push_back(i);
		}
	}
	res.push_back(1);
	if (rb < r) {
		vector<int> r1 = solve(rb+1,r);
		for (auto i : r1) {
			res.push_back(i);
		}
	}
	return {res};
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	//precompute
	pw[0] = 1, ip[0] = 1;
	for (int i=1; i<2*mxn; i++) {
		pw[i] = p*pw[i-1]%mod;
		ip[i] = ksm(p)*ip[i-1]%mod;
	}
	
	string ss; cin >> ss;
	n = sz(ss);
	for (int i=0; i<n; i++) {
		s[i] = ss[i]-'a'+1;
	}
	
	int cv=0;
	for (int i=0; i<n; i++) {
		hv[i] = cv;
		if (i && stk[sz(stk)-1]==s[i]) {
			cv -= stk[sz(stk)-1];
			cv = cv * ip[1] % mod;
		} else {
			stk.push_back(s[i]);
			cv = (cv * pw[1] + s[i])%mod;
		}
	}
	hv[n]=cv;
	if (cv) {
		cout<<-1; return 0;
	}
	for (int i=1; i<=n; i++) {
		if (!ep.count({s[i-1],hv[i]})) {
			ep[{s[i-1],hv[i]}] = {};
		}
		ep[{s[i-1],hv[i]}].push_back(i-1);
	}
	vector<int> ans = solve(0,n-1);
	for (auto i: ans) {
		cout << (i ? ")" : "(");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 20ms
memory: 6716kb

input:

abbaaa

output:

(()())

result:

ok single line: '(()())'

Test #2:

score: 0
Wrong Answer
time: 21ms
memory: 6596kb

input:

cbbbbccbbccbbbbbbc

output:

-1

result:

wrong answer 1st lines differ - expected: '(((((((()))())))))', found: '-1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%