oj.uz

Submission #704961

# Submission time Handle Problem Language Result Execution time Memory
704961 2023-03-03T07:20:01 Z PixelCat Superpozicija (COCI22_superpozicija) C++14
10 / 110
 18 ms 3284 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];
char t[MAXN];
int sel[MAXN];

void solve(int n, vector<pii> &p) {
    vector<int> st;
    int now = 0;
    if(n % 2) goto FAIL;
    for(int i = 2; i <= n * 2; i += 2) {
        if(s[i] == s[i - 1]) {
            t[i / 2] = s[i];
        } else {
            t[i / 2] = '.';
        }
    }
    For(i, 1, n) {
        if(t[i] == '(') {
            now++;
        } else if(t[i] == ')') {
            now--;
            if(now < 0) {
                if(!sz(st)) goto FAIL;
                t[st.back()] = '(';
                st.pop_back();
                now += 2;
            }
        } else {
            if(now > 0) {
                now--;
                t[i] = ')';
                st.eb(i);
            } else {
                now++;
                t[i] = '(';
            }
        }
    }
    // For(i, 1, n) cout << t[i];
    // cout << "\n";
    if(now) goto FAIL;
    For(i, 0, n - 1) {
        auto it = p[i];
        if(t[it.S / 2] == s[it.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;
        For(i, 1, n * 2) sel[i] = 0;
        cin >> (s + 1);
        vector<pii> p(n);
        for(auto &i:p) {
            cin >> i.F >> i.S;
            // assert(i.F + 1 == i.S);
            assert(s[i.F] == s[i.S]);
            if(s[i.F] == '(') sel[i.F] = 1;
            else sel[i.S] = 1;
        }
        // solve(n, p);
        int now = 0;
        bool ac = true;
        For(i, 1, n * 2) if(sel[i]) {
            if(s[i] == '(') now++;
            else now--;
            if(now < 0) ac = false;
        }
        if(!ac || now != 0) cout << "-1\n";
        else {
            For(i, 0, n - 1) {
                auto x = p[i];
                if(sel[x.F]) cout << "0";
                else cout << "1";
                cout << " \n"[i == n - 1];
            }
        }
    }
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 348 KB Output is correct
2 Correct 15 ms 676 KB Output is correct
3 Correct 14 ms 980 KB Output is correct
4 Correct 14 ms 1276 KB Output is correct
5 Correct 13 ms 1632 KB Output is correct
6 Correct 9 ms 2004 KB Output is correct
7 Correct 12 ms 2260 KB Output is correct
8 Correct 14 ms 2644 KB Output is correct
9 Correct 15 ms 2900 KB Output is correct
10 Correct 18 ms 3284 KB Output is correct

Subtask #3
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 #4
0 / 70.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 -