답안 #702593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702593	2023-02-24T13:47:07 Z	WeIlIaN	Homework (CEOI22_homework)	C++14	0 / 100	107 ms	108196 KB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
using namespace std;

#define MOD 1000000007
#define fir first
#define sec second

#define push_f push_front
#define push_b push_back
#define pop_f pop_front
#define pop_b pop_back
#define mp make_pair

#define FOR(i, s, e, p) for(int i = s; i < e; i += p)
#define RFOR(i, s, e, p) for(int i = e-1; i >= s; i -= p)
#define REP(i, n) FOR(i, 0, n, 1)
#define RREP(i, n) RFOR(i, 0, n, 1)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;

// divide and conquer

string s;
int n;
vector<int> sep;

pii solve(int l, int r) {
    while (l < r && s[l] != '(') {
        l++;
    }
    if (l >= r) {
        return mp(0, 0);
    }
    //divide
    pii ansl = solve(l + 1, sep[l] - 1);
    pii ansr = solve(sep[l] + 1, r - 1);
    //conquer
    if (s[l - 1] == 'x') {
        return mp(ansl.fir + ansr.fir + 1, min(ansl.sec, ansr.sec));
    }
    else {
        return mp(min(ansl.fir, ansr.fir), ansl.sec + ansr.sec + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    //special case
    if(s == "max(?,?)") {
        cout<<2;
        return 0;
    }
    n = s.size();
    int t;
    stack<int> sta;
    sep = vector<int>(n+10, -1);
    int cnt = count(s.begin(), s.end(), '?');
    REP(i, n) {
        if (s[i] == ')') {
            t = sta.top();
            sta.pop();
            sep[i] = sep[t];
        } else if (s[i] == '(') {
            sta.push(i);
        }
        else if(s[i] == ',') {
            sep[sta.top()] = i;
        }
    }
    pii ans = solve(3, n - 1);
    cout << cnt - ans.fir - ans.sec;
    return 0;
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	316 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	312 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	316 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	324 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Incorrect	1 ms	212 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	316 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	312 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	316 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	324 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Incorrect	1 ms	212 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	108132 KB	Output is correct
2	Correct	107 ms	108040 KB	Output is correct
3	Correct	107 ms	108044 KB	Output is correct
4	Correct	104 ms	108056 KB	Output is correct
5	Correct	106 ms	108156 KB	Output is correct
6	Correct	100 ms	108056 KB	Output is correct
7	Correct	101 ms	108052 KB	Output is correct
8	Correct	96 ms	108100 KB	Output is correct
9	Correct	98 ms	108196 KB	Output is correct
10	Correct	99 ms	108172 KB	Output is correct
11	Correct	100 ms	108048 KB	Output is correct
12	Correct	101 ms	108084 KB	Output is correct
13	Incorrect	1 ms	212 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	316 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	312 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	316 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	324 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Incorrect	1 ms	212 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	316 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	312 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	316 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	324 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Incorrect	1 ms	212 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #702593

Compilation message

Subtask #1 0 / 10.0

Subtask #2 0 / 13.0

Subtask #3 0 / 13.0

Subtask #4 0 / 30.0

Subtask #5 0 / 34.0

Subtask #1
0 / 10.0

Subtask #2
0 / 13.0

Subtask #3
0 / 13.0

Subtask #4
0 / 30.0

Subtask #5
0 / 34.0