wa on #10

P3952 [NOIP2017 提高组] 时间复杂度

jJHZ @ 2025-01-05 13:02:05

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define TLE  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long

using namespace std;
struct Luogu_P_3952
{
    /* data */
    string val;
    int  stop = 0,ans;
};

stack<Luogu_P_3952> s;
map<string, bool> mp;
void mian(){
    while(!s.empty()){
        s.pop();
    }
    mp.clear();
    int n = 0, ans = 0, now = 0;
    int stop = 0;
    int ERR = 0;
    string standard;
    cin >> n >> standard;
    for (int i = 1; i <= n;i++){

        if(stop==0){
            ans = max(ans, now);

        }
        if(s.empty()){
            now = 0;
            stop = 0;
        }
        if(!s.empty()){
            stop = s.top().stop;
            now = s.top().ans;
        }
        string kind, var, start, end;
        cin >> kind;
        if(kind=="F"){
            cin >> var >> start >> end;
            if(mp[var]==true){
                ERR = 1;
                continue;
            }else{
                mp[var] = true;

                if(start=="n"||(start>=end&&end!="n")){
                    ans = max(ans, now);
                    stop = 1;
                }
                else if(end=="n"){
                    now++;
                }
            }
            Luogu_P_3952 x;
            x.val = var;
            x.stop = stop;
            x.ans = now;
            s.push(x);
        }else{
            if(s.empty()){
                ERR = 1;
                continue;
            }
            if(now>0){
                now--;
            }
            mp[s.top().val] = false;
            s.pop();
        }
        //cout << i + 1 << ":" << now << ' ' << ans << ' ' << stop << '\n';
    }
    if (stop == 0)
    {
        ans = max(ans, now);
        now = 0;
    }
    if(!s.empty()||ERR==1){
        cout << "ERR" << '\n';
        return;
    }
    if(ans==0){
        if(standard=="O(1)"){
            cout << "Yes" << '\n';
        }
        else{
            cout << "No" << '\n';
        }
    }else{
        string truth="O(n^";
        string m;
        m = to_string(ans);
        m += ')';
        truth += m;

        if(standard==truth){
            cout << "Yes" << '\n';
        }
        else{
            cout << "No" << '\n';
        }
    }
}
int main()
{
    TLE;
    int T;
    cin >> T;
    while(T--){
        mian();
    }

    return 0;
}

|