Submission #726571

#	Time	Username	Problem	Language	Result	Execution time	Memory
726571		ReLice	Homework (CEOI22_homework)	C++14	100 / 100	215 ms	70688 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define bc back()
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=7e6+7;
string s;
ll n,md[N],a=0;
ll rec(ll l,ll r){
    ll c=0,mid;
    if(s[l+4]=='?'){
        mid=l+5;
    }
    else{
        mid=md[l+4]+1;
    }
    if(s[l+1]=='i' && s[l+2]=='n'){
        if(s[l+4]=='?'){
            if(s[r-1]=='?'){
                return 2;
            }
            return 1+rec(mid+1,r-1);
        }
        else if(s[r-1]=='?'){
            return rec(l+4,mid-1)+1;
        }
        return rec(l+4,mid-1)+rec(mid+1,r-1);
    }
    else{
        if(s[l+4]=='?' || s[r-1]=='?'){
            return 1;
        }
        return min(rec(l+4,mid-1),rec(mid+1,r-1));
    }
}
ll rec2(ll l,ll r){
    ll c=0,mid;
    if(s[l+4]=='?'){
        mid=l+5;
    }
    else{
        mid=md[l+4]+1;
    }
    if(s[l+1]=='i' && s[l+2]=='n'){
        if(s[l+4]=='?' || s[r-1]=='?'){
            return 1;
        }
        return min(rec2(l+4,mid-1),rec2(mid+1,r-1));
    }
    else{
        if(s[l+4]=='?'){
            if(s[r-1]=='?'){
                return 2;
            }
            return 1+rec2(mid+1,r-1);
        }
        else if(s[r-1]=='?'){
            return rec2(l+4,mid-1)+1;
        }
        return rec2(l+4,mid-1)+rec2(mid+1,r-1);
    }
}
void solve(){
    ll i,j,q,sum=0,b,c=0,c2=0;
    ll m,i1=-1,l=-5,r=inf;
    ll k,mn=inf,d,mx=-inf;
    cin>>s;
    n=s.sz;
    vector <ll> v;
    for(i=0;i<n;i++){
        if(s[i]=='?') sum++;
        if(s[i]=='(') {
            v.pb(i-3);
        }
        if(s[i]==')') {
            md[v.bc]=i;
            v.pop_back();
        }
    }
    c=rec(0,n-1);
    c2=rec2(0,n-1);
    cout<<sum-c-c2+2<<endl;
}
signed main(){
    //start();
    //fre("");
    ll t=1;
    //cin>>t;
    while(t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'long long int rec(long long int, long long int)':
Main.cpp:27:8: warning: unused variable 'c' [-Wunused-variable]
   27 |     ll c=0,mid;
      |        ^
Main.cpp: In function 'long long int rec2(long long int, long long int)':
Main.cpp:54:8: warning: unused variable 'c' [-Wunused-variable]
   54 |     ll c=0,mid;
      |        ^
Main.cpp: In function 'void solve()':
Main.cpp:81:10: warning: unused variable 'j' [-Wunused-variable]
   81 |     ll i,j,q,sum=0,b,c=0,c2=0;
      |          ^
Main.cpp:81:12: warning: unused variable 'q' [-Wunused-variable]
   81 |     ll i,j,q,sum=0,b,c=0,c2=0;
      |            ^
Main.cpp:81:20: warning: unused variable 'b' [-Wunused-variable]
   81 |     ll i,j,q,sum=0,b,c=0,c2=0;
      |                    ^
Main.cpp:82:8: warning: unused variable 'm' [-Wunused-variable]
   82 |     ll m,i1=-1,l=-5,r=inf;
      |        ^
Main.cpp:82:10: warning: unused variable 'i1' [-Wunused-variable]
   82 |     ll m,i1=-1,l=-5,r=inf;
      |          ^~
Main.cpp:82:16: warning: unused variable 'l' [-Wunused-variable]
   82 |     ll m,i1=-1,l=-5,r=inf;
      |                ^
Main.cpp:82:21: warning: unused variable 'r' [-Wunused-variable]
   82 |     ll m,i1=-1,l=-5,r=inf;
      |                     ^
Main.cpp:83:8: warning: unused variable 'k' [-Wunused-variable]
   83 |     ll k,mn=inf,d,mx=-inf;
      |        ^
Main.cpp:83:10: warning: unused variable 'mn' [-Wunused-variable]
   83 |     ll k,mn=inf,d,mx=-inf;
      |          ^~
Main.cpp:83:17: warning: unused variable 'd' [-Wunused-variable]
   83 |     ll k,mn=inf,d,mx=-inf;
      |                 ^
Main.cpp:83:19: warning: unused variable 'mx' [-Wunused-variable]
   83 |     ll k,mn=inf,d,mx=-inf;
      |                   ^~
Main.cpp: In function 'void fre(std::string)':
Main.cpp:15:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:15:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34