QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#661820#7894. Many Many HeadsYuuWA 0ms3880kbC++233.2kb2024-10-20 18:21:072024-10-20 18:21:07

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 18:21:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2024-10-20 18:21:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

//  The 2023 ICPC Asia Jinan Regional Contest 

void sol(){
    std::string s;
    std::cin>>s;

    int n = s.length();
    std::vector<int>vis(n);
    for(int i = 0;i<n;i++) {
        if(s[i] =='(' || s[i] == ')') vis[i] = 1;
    }

    std::vector<int>p1,p2;
    for(int i = 0;i<n;i++){
        if(s[i] =='(' || s[i] == ')'){
            p1.push_back(i);
        }else{
            p2.push_back(i);
        }
    }

    if(n == 2){
        std::cout<<"YES\n";
        return ;
    }

    if(p1.size() == 0){
        std::cout<<(p2.size() == 2?"YES\n":"NO\n");
        return ;
    }

    if(p2.size() == 0){
        std::cout<<(p1.size() == 2?"YES\n":"NO\n");
        return ;
    }

    for(int i = 1;i<p1.size();i++){
        int d = p1[i] - p1[i - 1] - 1;
        if(d > 2){
            std::cout<<"NO\n";
            return ;
        }
    }

    for(int i = 1;i<p2.size();i++){
        int d = p2[i] - p2[i - 1] - 1;
        if(d > 2){
            std::cout<<"NO\n";
            return ;
        }
    }

    if(p2.size() == 2){
        if(p2[0] >= 2 && n - p2[1] >= 2){
            std::cout<<"NO\n";
            return ;
        }
        if(vis[0] == vis[1] && vis[1] == vis[2]){
            std::cout<<"NO\n";
            return ;
        }
        if(vis[n - 1] == vis[n - 2] && vis[n - 2] == vis[n - 3]){
            std::cout<<"NO\n";
            return ;
        }
        std::cout<<"YES\n";
        return ;
    }

    if(p1.size() == 2){
        if(p1[0] >= 2 && n - p1[1] >= 2){
            std::cout<<"NO\n";
            return ;
        }
         if(vis[0] == vis[1] && vis[1] == vis[2]){
            std::cout<<"NO\n";
            return ;
        }
        if(vis[n - 1] == vis[n - 2] && vis[n - 2] == vis[n - 3]){
            std::cout<<"NO\n";
            return ;
        }
        std::cout<<"YES\n";
        return ;
    }

    std::vector<std::array<int, 2>>vec1;
    std::vector<std::array<int, 2>>vec2;
    
    for(int i = 0;i<n - 1;i++){
        if(vis[i] == vis[i + 1]){
            if(vis[i] == 0){
                vec1.push_back({i, i + 1});
            }else{
                vec2.push_back({i, i + 1});
            }
        }
        
    }

    for(int i = 1;i<vec1.size();i++){
        auto [l, r] = vec1[i];
        if(vis[l] == vis[l - 1]){
            std::cout<<"NO\n";
            return ;
        }
        auto [l1, r1] = vec1[i - 1];
        if(r1 + 3 == l){
            if(vis[r1 + 1] == vis[r1 + 2]){
                std::cout<<"NO\n";
                return ;
            }
        }
    }

    for(int i = 1;i<vec2.size();i++){
        auto [l, r] = vec2[i];
        if(vis[l] == vis[l - 1]){
            std::cout<<"NO\n";
            return ;
        }
        auto [l1, r1] = vec2[i - 1];
        if(r1 + 3 == l){
            if(vis[r1 + 1] == vis[r1 + 2]){
                std::cout<<"NO\n";
                return ;
            }
        }
    }

    std::cout<<"YES\n";
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1; std::cin>>t;
    while(t--) sol();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

6
))
((()
[()]
()[()]()
([()])
([])([])

output:

YES
NO
YES
NO
YES
NO

result:

ok 6 token(s): yes count is 3, no count is 3

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

2
(([([[([
]]))])]])]

output:

YES
YES

result:

wrong answer expected NO, found YES [2nd token]