Submission #774982

#	Time	Username	Problem	Language	Result	Execution time	Memory
774982		hgmhc	Homework (CEOI22_homework)	C++17	100 / 100	100 ms	116032 KiB

Main

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ii = pair<int,int>;
using ll = long long;
#define siz(x) int((x).size())
#define all(x) begin(x),end(x)
#define mp make_pair

const int N = 7e6+3;
int n, m;
char s[N];
int match[N];

int a, b, c;

void dfs(int x, int y) {
    if (y-x == 0) { a=1,b=1,c=1; return; }
    int x1, y1, x2, y2, z1, z2, p=-1;
    if (s[x+4] == '?') p = x+4;
    else p = match[x+7];
    dfs(x+4,p), x1=a,y1=b,z1=c;
    dfs(p+2,y-1), x2=a,y2=b,z2=c;
    if (s[x+1] == 'i') { a=min(x1,x2),b=y1+y2-1,c=z1+z2; return; }
    a=x1+x2,b=z1+z2-min(z1-y1,z2-y2),c=z1+z2;
}

int main() {
    scanf("%s", s+1);
    m = strlen(s+1);
    n = count(s+1,s+m+1,'?');
    stack<int> st;
    rep(i,1,m) {
        if (s[i] == '(') st.push(i);
        if (s[i] == ')') match[st.top()] = i, st.pop();
    }
    dfs(1,m);
    printf("%d", b-a+1);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%s", s+1);
      |     ~~~~~^~~~~~~~~~~

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