結果

問題 No.2143 Only One Bracket
ユーザー
提出日時 2022-12-02 22:47:38
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,506 bytes
コンパイル時間 2,604 ms
コンパイル使用メモリ 205,268 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-18 07:56:07
合計ジャッジ時間 2,889 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
namespace atcoder{};using namespace atcoder;

using ull = uint64_t;
using ll = int64_t;
using vi = vector<int>;
using vll = vector<ll>;
using vs = vector<string>;
using ld = long double;
using P = pair<ll,ll>;
using G = vector<vector<int>>;

#ifdef MYDEBUG
#pragma once

#define LO(...) fprintf(stderr, __VA_ARGS__)
#define debug(x) cerr << "\033[33m(line:" << __LINE__ << ") " << #x << ": " << x << "\033[m" << endl

template<class C> string join(const C& c){stringstream ss; for(auto it=c.begin(); it!=c.end();it++){ss << *it;if(it!=c.end())ss<<", ";}return ss.str();}
template<class C> ostream &operator<<(ostream &os, const vector<C>& c){for(auto it=c.begin(); it!=c.end();it++){os << *it;if(it!=c.end())os<<", ";}return os;}
#else
#define LO(...) (void)0
#define debug(x) (void)0
#endif

#define reps(i,a,n) for(ll i##_len = (ll)(n), i = (a); i < i##_len; ++i)
#define rep(i,n) reps(i,0,(n))
#define rrep(i,n) reps(i,1,(n)+1)
#define repd(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrepd(i,n) for(ll i=(n);i>=1;i--)

#define inp(i) ll i; cin >> i;
#define inps(s) string s; cin >> s;
#define inpp(p) cin >> (p).first >> (p).second
#define inpv(v,N) vll v(N);rep(i,N)cin>>v[i];
#define inpg(g,N,M) g.resize(N);rep(i,M){inp(a);inp(b);a--,b--;g[a].push_back(b);g[b].push_back(a);}
#define all(v) begin(v),end(v)
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
void YESNO(bool b){cout<<(b?"YES\n":"NO\n");} void yesno(bool b){cout<<(b?"yes\n":"no\n");} void YesNo(bool b){cout<<(b?"Yes\n":"No\n");}

#define SP cout << " "
#define ENDL cout << "\n"
#define ou(i) cout << (i)
#define ous(i) cout << (i) << " "
#define oul(i) cout << (i) << "\n"
#define setfp() cout << fixed << setprecision(16)

template<typename C> void ouv(const C &v){for(auto &&e:v){cout << e;if(&e != &v.back()) cout << ' ';}cout << "\n";}
template<typename C> void ouvadd(const C &v){for(auto &&e:v){cout << e+1;if(&e != &v.back()) cout << ' ';}cout << "\n";}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

inline ll lg(ll __n) { return sizeof(ll) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,1,-1,-1};

constexpr ll INF = 1e18;

bool ok(const string &a){
    ll cur = 0;
    for(char c:a){
        if(c=='('){
            cur++;
        }else{
            cur--;
        }
        if(cur < 0){
            return 0;
        }
    }
    return cur == 0;
}

vector<string> f(ll n){
    srand(time(NULL));
    while(1){
        vector<string> a;
        ll t1 = 0;
        ll t2 = 0;
        rep(i,n){
            string s = "";
            if(n*n-t1-t2<0)break;
            ll c = rand() % (min<ll>(n*n-t1-t2+1,3*n+1)) + 1;
            //c = i+1;
            rep(j,c){
                if(rand()%2){
                    s += "(";
                    t1++;
                }else{
                    s += ")";
                    t2++;
                }
            }
            a.push_back(s);
        }
        if(t1!=t2)continue;
        if(t1+t2 > n * n)continue;

        vll p(n);
        iota(all(p), 0);
        ll ans = 0;
        do{
            string k;
            //bool ok = 1;
            ll cur = 0;
            rep(i,n){
                k += a[p[i]];

                //for(char c:a[p[i]]){
                //    if(c=='('){
                //        cur++;
                //    }else{
                //        cur--;
                //    }
                //    if(cur < 0){
                //        ok = 0;
                //    }
                //}
                //ok = ok && (cur == 0);
            }
            ans += ok(k);
            if(ans>=2)break;
        }while(next_permutation(all(p)));
        if(ans == 1){
            return a;
        }
    }
}

int main(){
    inp(N);
    //auto t = f(N);
    //rep(i,t.size()){
    //    oul("oul(\"" + t[i] + "\");");
    //}
    //return 0;
    if(N==2){
        oul(")");
        oul("(()");
    //}else if(N==3){
    //    oul("(");
    //    oul("((())");
    //    oul("))");
    //}else if(N==4){
    //    oul("(");
    //    oul(")()");
    //    oul(")))(");
    //    oul(")(((");
    //}else if(N==5){
    //    oul(")((");
    //    oul("))()(");
    //    oul(")))((");
    //    oul("((()");
    //    oul(")");
    //}else if(N==6){
    //    oul("((()()");
    //    oul(")))(((");
    //    oul(")())(");
    //    oul(")))((");
    //    oul(")((");
    //    oul(")");

}else if(N==3){
    oul("(");
    oul(")()(");
    oul("())");
}else if(N==4){
    oul("))(");
    oul(")");
    oul("()))()((");
    oul("((");
}else if(N==5){
    oul("(");
    oul(")))(");
    oul(")))((");
    oul(")");
    oul(")((((");
}else if(N==6){
    oul("(");
    oul("))");
    oul(")(())((");
    oul("))(((");
    oul("))(())(()");
    oul("()())))(((");
}else if(N==7){
    oul("()())))(()(()");
    oul("(");
    oul(")()((");
    oul(")))((((");
    oul("()())(()))(((");
    oul(")(())))(");
    oul(")");
}else if(N==8){
    oul(")()()())())((((");
    oul("))()()((((())");
    oul("))))((((()((())))");
    oul(")())()()(");
    oul(")((");
    oul(")))((");
    oul("(");
    oul(")");
}else{
    auto t = f(N);
    rep(i,t.size()){
        oul("oul(\"" + t[i] + "\");");
    }
}

return 0;
}
0