제출 #1115709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115709		bleahbleah	괄호 문자열 (CEOI16_match)	C++17	100 / 100	80 ms	18592 KiB

match

#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';
	
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63