結果
| 問題 | No.3539 Parentheses Square |
| コンテスト | |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2026-05-08 22:24:05 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 63 ms / 2,000 ms |
| コード長 | 5,746 bytes |
| 記録 | |
| コンパイル時間 | 2,000 ms |
| コンパイル使用メモリ | 128,464 KB |
| 実行使用メモリ | 24,832 KB |
| 最終ジャッジ日時 | 2026-05-08 22:24:11 |
| 合計ジャッジ時間 | 4,516 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 41 |
ソースコード
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }
V<string> concrete(string T, ll mx){
ll N = T.size() / 2;
V<V<int>> dp(N+2, V<int>(N+2));
dp[0][0] = 1;
REP(i,N+1) REP(j,N+1) if(i+j < N*2) if(dp[i][j]){
if(i > j){ dp[i][j] = 0; continue; }
if(T[i+j] != ')') dp[i][j+1] = 1;
if(T[i+j] != '(') dp[i+1][j] = 1;
}
V<string> ans;
string buf = T;
auto dfs = [&](auto& dfs, ll i, ll j) -> void {
if(ans.size() == mx) return;
if(dp[i][j] == 0) return;
if(i + j == 0){ ans.push_back(buf); return; }
if(j && T[i+j-1] != ')'){ buf[i+j-1] = '('; dfs(dfs, i, j-1); }
if(i && T[i+j-1] != '('){ buf[i+j-1] = ')'; dfs(dfs, i-1, j); }
};
dfs(dfs, N, N);
return ans;
}
#include <utility>
namespace nachia{
template<class Elem>
class CsrArray{
public:
struct ListRange{
using iterator = typename std::vector<Elem>::iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
Elem& operator[](int i) const { return begi[i]; }
};
struct ConstListRange{
using iterator = typename std::vector<Elem>::const_iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
const Elem& operator[](int i) const { return begi[i]; }
};
private:
int m_n;
std::vector<Elem> m_list;
std::vector<int> m_pos;
public:
CsrArray() : m_n(0), m_list(), m_pos() {}
static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
CsrArray res;
res.m_n = n;
std::vector<int> buf(n+1, 0);
for(auto& [u,v] : items){ ++buf[u]; }
for(int i=1; i<=n; i++) buf[i] += buf[i-1];
res.m_list.resize(buf[n]);
for(int i=(int)items.size()-1; i>=0; i--){
res.m_list[--buf[items[i].first]] = std::move(items[i].second);
}
res.m_pos = std::move(buf);
return res;
}
static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
CsrArray res;
res.m_n = pos.size() - 1;
res.m_list = std::move(list);
res.m_pos = std::move(pos);
return res;
}
ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
int size() const { return m_n; }
int fullSize() const { return (int)m_list.size(); }
};
} // namespace nachia
namespace nachia{
std::vector<int> BipertiteMatching(int N1, int N2, const std::vector<std::pair<int, int>>& edges){
std::vector<int> R(N2, -1);
std::vector<int> L(N1, -1);
auto E = CsrArray<int>::Construct(N1, edges);
while(true){
std::vector<int> bfs, dist(N1, -1), P(N1, -1);
for(int i=0; i<N1; i++) if(L[i] == -1){ bfs.push_back(i); dist[i] = 0; }
int maxD = N1 + 1;
for(size_t i=0; i<bfs.size(); i++){
int p = bfs[i];
if(dist[p] >= maxD) break;
for(int e : E[p]) if(L[p] != e){
if(R[e] >= 0){
if(dist[R[e]] < 0){
dist[R[e]] = dist[p] + 1;
P[R[e]] = p;
bfs.push_back(R[e]);
}
}
else maxD = dist[p];
}
}
if(maxD > N1) break;
std::vector<int> I(N1, 0);
for(int s=0; s<N1; s++) if(L[s] == -1){
int p = s, p2;
while(p >= 0){
if(I[p] == E[p].size()){ p = P[p]; continue; }
int q = E[p][I[p]++];
int r = R[q];
if(r == -1){ p2 = q; break; }
if(dist[r] != dist[p] + 1) continue;
P[r] = p;
p = r;
}
if(p < 0) continue;
while(p >= 0){
R[p2] = p;
std::swap(L[p], p2);
p = P[p];
}
}
}
std::vector<int> ans;
for(int i=0; i<(int)edges.size(); i++){
auto& e = edges[i];
if(L[e.first] == e.second){ L[e.first] = -1; ans.push_back(i); }
}
return ans;
}
} // namespace nachia
void testcase(){
ll N; cin >> N;
V<string> T(N); REP(i,N) cin >> T[i];
if(N%2 == 1){ cout << "-1\n"; return; }
V<string> mapping;
V<V<string>> conc(N);
REP(i,N){
conc[i] = concrete(T[i], N);
for(auto& a : conc[i]) mapping.push_back(a);
}
REP(i,N) if(conc[i].empty()){ cout << "-1\n"; return; }
sort(mapping.begin(), mapping.end());
mapping.erase(unique(mapping.begin(), mapping.end()), mapping.end());
V<pair<int,int>> sha;
REP(i,N) for(auto& a : conc[i]) sha.push_back({i,lower_bound(mapping.begin(), mapping.end(), a) - mapping.begin()});
auto mch = nachia::BipertiteMatching(N, mapping.size(), sha);
V<ll> ch(N, -1);
for(auto a : mch) if(a >= 0) ch[sha[a].first] = sha[a].second;
REP(i,N) if(ch[i] < 0){ cout << "-1\n"; return; }
REP(i,N) cout << mapping[ch[i]] << "\n";
}
int main(){
cin.tie(0)->sync_with_stdio(0);
testcase();
return 0;
}