oj.uz

Submission #704927

# Submission time Handle Problem Language Result Execution time Memory
704927 2023-03-03T06:53:01 Z PixelCat Palindromi (COCI22_palindromi) C++14
0 / 110
 3 ms 824 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200010;

char s[MAXN];
int sel[MAXN];

void solve(int n, vector<pii> &p) {
    vector<int> st;
    int now = 0;
    if(n % 2) goto FAIL;
    for(auto &i:p) {
        if(s[i.F] == s[i.S]) {
            sel[i.F] = 2;
        }
    }
    for(int i = 1; i < n * 2; i += 2) {
        if(max(sel[i], sel[i + 1]) == 2) {
            if(s[i] == '(') {
                now++;
            } else {
                now--;
                if(now < 0) {
                    if(!sz(st)) goto FAIL;
                    auto it = st.back();
                    sel[it] = 0;
                    sel[(it % 2 ? it + 1 : it - 1)] = 1;
                    now += 2;
                    st.pop_back();
                }
            }
        } else {
            if(now > 0) {
                now--;
                if(s[i] == ')') {
                    st.eb(i);
                    sel[i] = 1;
                } else {
                    st.eb(i + 1);
                    sel[i + 1] = 1;
                }
            } else {
                now++;
                if(s[i] == '(') {
                    sel[i] = 1;
                } else {
                    sel[i + 1] = 1;
                }
            }
        }
    }
    For(i, 0, n - 1) {
        if(sel[p[i].F]) cout << "0";
        else cout << "1";
        cout << " \n"[i == n - 1];
    }
    return;
    FAIL:
    cout << "-1\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nya ><
    int N; cin >> N;
    while(N--) {
        int n; cin >> n;
        cin >> (s + 1);
        vector<pii> p(n);
        for(auto &i:p) {
            cin >> i.F >> i.S;
            assert(i.F + 1 == i.S);
        }
        solve(n, p);
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 824 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -