結果

問題 No.3144 Parentheses Modification and Rotation (01 Ver.)
コンテスト
ユーザー Leal-0
提出日時 2025-05-16 22:37:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,093 bytes
コンパイル時間 1,707 ms
コンパイル使用メモリ 201,220 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-16 22:37:58
合計ジャッジ時間 3,075 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 3 WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__

int main() {
int n;
    string s;
    cin>>n>>s;


    vector<ll> p(n+1,0);
    rep(i,n){
        p[i+1]=p[i]+(s[i]=='('?1:-1);
    }
    ll mn=p[0];
    int t=0;
    srep(i,1,n){
        if(p[i]<=mn){
            mn=p[i];
            t=i;
        }
    }
    int k=(n-(t%n))%n;

    ll balance=0, flips=0;
    rep(i,n){
        char c=s[(i+k)%n];
        if(c=='(') balance++;
        else        balance--;
        if(balance<0){
            flips++;
            balance=1;
        }
    }
    flips+=balance/2;

    cout<<flips<<nl;
    int r,m; cin>>r>>m; //namesugi
    return 0;

}
/////// library zone ///////
#else
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" ";
#define INF 9223300000000000000ll
#define Winf 5e12
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>
#define vc vector<char>



ll calc_min(const string &s){
    stack<ll> st;
    for(char c:s){
        if(c=='('){
            st.push(0);
        } else {
            ll cur=st.top(); st.pop();
            ll sc=(cur==0 ? 2 : cur+1);
            if(st.empty()) st.push(sc);
            else{
                ll t=st.top(); st.pop();
                st.push(t+sc);
            }
        }
    }
    return st.empty()?0:st.top();
}

bool taio(const string &s){
    ll bal=0;
    for(char c:s){
        if(c=='(') bal++;
        else{
            if(bal==0) return false;
            bal--;
        }
    }
    return bal==0;
}


template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

void no() { cout<<"No"<<nl;}
void yes() { cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}

ll sum(vector<ll>& a) {
    ll ans=0;
    for(auto i:a) ans+=i;
    return ans;
}

#endif
0