oj.uz

Submission #1115709

# Submission time Handle Problem Language Result Execution time Memory
1115709 2024-11-20T20:39:23 Z bleahbleah Match (CEOI16_match) C++17
100 / 100
 80 ms 18592 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
#define sz(x) ((int)(x).size())

const int nmax = 2e5 + 5;
const int mod = 998244853;

using ll = long long;

struct Mint {
	int val;
	Mint(ll x = 0): val((x % mod + mod) % mod) {;}
	Mint operator +(const Mint& x) const { return Mint(val + x.val); }
	Mint operator -(const Mint& x) const { return Mint(val - x.val); }
	Mint operator *(const Mint& x) const { return Mint((ll)val * x.val); }
	Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
	Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
	Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
	Mint operator ^(int b) const {
		Mint accum = 1, a = *this;
		while(b) {
			accum = (b & 1? accum * a : accum);
			a *= a;
			b >>= 1;
		}
		return accum;
	}
	Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
	Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};

Mint p[nmax][2];

struct hsh {
	Mint v[2];
	int len;
	hsh() { v[0] = v[1] = len = 0; }
	hsh(int a) { v[0] = v[1] = a; len = 1; }
	hsh(Mint a, Mint b, int c) { v[0] = a; v[1] = b; len = c; }
	hsh operator +(const hsh& x) const {
		return hsh(v[0] * p[0][x.len] + x.v[0], v[1] * p[1][x.len] + x.v[1], len + x.len);
	}
	ll operator ()() const {
		return v[0].val * mod + v[1].val;
	}
	bool operator < (const hsh& x) const {
		return (*this)() < x();
	}
};

hsh level[nmax];
void initlevels(string s) {
	vector<int> st;
	vector<hsh> pref;
	pref.emplace_back(hsh());
	for(int i = 1; i < sz(s); i++) {
		if(sz(st) == 0 || st.back() != s[i]) st.emplace_back(s[i]), pref.emplace_back(pref.back() + hsh(s[i]));
		else st.pop_back(), pref.pop_back();
		level[i] = pref.back();
	}
	if(sz(st) != 0) { cout << "-1\n"; exit(0); }
	return;
}

map<hsh, set<int>> atr[256];

int getprev(int x, const set<int>& s) {
	auto it = s.lower_bound(x);
	if(it == s.begin()) return -1;
	return *prev(it);
}

signed main() {
	{
		mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
		p[0][0] = p[0][1] = 1;
		p[1][0] = rng() % (mod - 500) + 100;
		p[1][1] = rng() % (mod - 502) + 99;
		for(int i = 2; i < nmax; i++) 
			p[i][0] = p[i - 1][0] * p[1][0],
			p[i][1] = p[i - 1][1] * p[1][1];
	}
	
	string s;
	cin >> s;
	s = "$" + s;
	initlevels(s);
	
	for(int i = 1; i < sz(s); i++) {
		atr[s[i]][level[i - 1]].emplace(i);
	}
	vector<int> st;
	vector<int> idx;
	vector<int> invidx;
	
	invidx.emplace_back(sz(s) + 1);
	
	string rez = "";
	
	for(int i = 1; i < sz(s); i++) {
		int ch = s[i];
		// cerr << i << '\t' << (char)ch << '\n';
		
		if(invidx.back() == i) {
			rez += ')';
			st.pop_back();
			idx.pop_back();
			invidx.pop_back();
		}
		else if(sz(st) == 0 || st.back() != ch) {
			rez += '(';
			st.emplace_back(ch);
			idx.emplace_back(i);
			invidx.emplace_back(getprev(invidx.back(), atr[ch][level[i]]));
			assert(idx.back() < invidx.back());
		}
		else {
			st.emplace_back(ch);
			idx.emplace_back(i);
			invidx.emplace_back(getprev(invidx.back(), atr[ch][level[i]]));
		
			if(idx.back() < invidx.back()) rez += '(';
			else {
				rez += ')';
				idx.pop_back(); idx.pop_back(); 
				st.pop_back(); st.pop_back(); 
				invidx.pop_back(); invidx.pop_back(); 
			}
		}
	}
	
	cout << rez << '\n';
	
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:92:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   92 |   atr[s[i]][level[i - 1]].emplace(i);
      |           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4176 KB Output is correct
2 Correct 5 ms 4344 KB Output is correct
3 Correct 5 ms 4176 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4176 KB Output is correct
2 Correct 5 ms 4344 KB Output is correct
3 Correct 5 ms 4176 KB Output is correct
4 Correct 5 ms 4432 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 6 ms 4432 KB Output is correct
7 Correct 5 ms 4432 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4176 KB Output is correct
2 Correct 5 ms 4344 KB Output is correct
3 Correct 5 ms 4176 KB Output is correct
4 Correct 5 ms 4432 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 6 ms 4432 KB Output is correct
7 Correct 5 ms 4432 KB Output is correct
8 Correct 7 ms 4944 KB Output is correct
9 Correct 7 ms 5200 KB Output is correct
10 Correct 8 ms 5456 KB Output is correct
11 Correct 8 ms 5456 KB Output is correct
12 Correct 41 ms 13720 KB Output is correct
13 Correct 50 ms 14724 KB Output is correct
14 Correct 49 ms 15252 KB Output is correct
15 Correct 27 ms 8780 KB Output is correct
16 Correct 27 ms 8996 KB Output is correct
17 Correct 49 ms 13764 KB Output is correct
18 Correct 29 ms 9284 KB Output is correct
19 Correct 70 ms 18568 KB Output is correct
20 Correct 40 ms 13984 KB Output is correct
21 Correct 80 ms 18592 KB Output is correct