#1151325 (C++17) No.3539 Parentheses Square

• 問題: No.3539 Parentheses Square
• ユーザー: nauclhlt
• 提出日時: 2026-03-05 00:05:05
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,623 bytes
• コンパイル時間: 2,075 ms
• コンパイル使用メモリ: 244,332 KB
• 実行使用メモリ: 16,808 KB
• 最終ジャッジ日時: 2026-05-08 20:53:23
• 合計ジャッジ時間: 7,493 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	WA * 3
other	AC * 2 WA * 6 TLE * 1 -- * 32

ソースコード

#include <bits/stdc++.h>
#include <atcoder/maxflow>

using namespace std;

using ll = long long;

bool check(string candidate, string t)
{
    for (int i = 0; i < candidate.size(); i++)
    {
        if (t[i] != '.' && candidate[i] != t[i]) return false;
    }

    return true;
}

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

    int N;
    cin >> N;
    assert(1 <= N && N <= 200);
    vector<string> T(N);
    for (int i = 0; i < N; i++)
    {
        cin >> T[i];
        assert(T[i].size() == N);
    }

    if (N % 2 == 1)
    {
        cout << "-1" << endl;
        return 0;
    }

    map<string, int> cand2idx;
    vector<string> idx2cand;
    vector<vector<int>> candidate;

    for (int i = 0; i < N; i++)
    {
        vector<int> close(N + 1);
        for (int j = 1; j <= N; j++)
        {
            close[j] = close[j - 1] + (T[i][j] != '(');
        }
        vector<char> buffer(N);
        vector<string> res;

        int calls = 0;
        auto f = [&](auto self, int pos, int depth, int opCount) -> void
        {
            calls++;
            if (res.size() == N)
                return;
            if (pos == T[i].size())
            {
                res.push_back(string(buffer.begin(), buffer.end()));
                return;
            }

            if (T[i][pos] == '.' || T[i][pos] == '(')
            {
                if (depth + 1 <= close[T[i].size()] - close[pos + 1] && T[i].size() - pos - 1 - (close[T[i].size()] - close[pos + 1]) + opCount + 1 <= N / 2)
                {
                    buffer[pos] = '(';
                    self(self, pos + 1, depth + 1, opCount + 1);
                }
            }

            if ((T[i][pos] == '.' || T[i][pos] == ')') && depth > 0)
            {
                buffer[pos] = ')';
                self(self, pos + 1, depth - 1, opCount);
            }
        };

        f(f, 0, 0, 0);

        cout << "CALLS=" << calls << endl;

        if (res.size() == 0)
        {
            cout << "-1" << endl;
            return 0;
        }

        for (int j = 0; j < res.size(); j++)
        {
            if (cand2idx.find(res[j]) == cand2idx.end())
            {
                cand2idx[res[j]] = idx2cand.size();
                idx2cand.push_back(res[j]);
                candidate.push_back({ i });
            }
            else
            {
                candidate[cand2idx[res[j]]].push_back(i);
            }
        }
    }

    if (candidate.size() < N)
    {
        cout << "-1" << endl;
        return 0;
    }

    cout << "GRAPH START" << endl;

    // C <= N^2
    int C = candidate.size();
    int source = 0;
    int sink = 1;
    int candHead = 2;
    int tHead = candHead + C;

    atcoder::mf_graph<int> g(2 + C + N);
    for (int i = 0; i < C; i++)
    {
        g.add_edge(source, candHead + i, 1);
    }
    for (int i = 0; i < N; i++)
    {
        g.add_edge(tHead + i, sink, 1);
    }

    for (int i = 0; i < C; i++)
    {
        for (int j = 0; j < candidate[i].size(); j++)
        {
            g.add_edge(candHead + i, tHead + candidate[i][j], 1);
        }
    }

    int maxflow = g.flow(source, sink);
    if (maxflow != N)
    {
        cout << "-1" << endl;
        return 0;
    }

    auto edges = g.edges();

    vector<string> S(N);

    for (int i = 0; i < edges.size(); i++)
    {
        if (edges[i].from == source || edges[i].to == sink) continue;

        if (edges[i].flow == 1)
        {
            S[edges[i].to - tHead] = idx2cand[edges[i].from - candHead];
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << S[i] << endl;
    }
}