제출 #704931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704931		PixelCat	Superpozicija (COCI22_superpozicija)	C++14	0 / 110	1 ms	468 KiB

Main

#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<pii> 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.F] = 0;
                    sel[it.S] = 1;
                    now += 2;
                    st.pop_back();
                }
            }
        } else {
            if(now > 0) {
                now--;
                if(s[i] == ')') {
                    st.eb(i, i + 1);
                    sel[i] = 1;
                } else {
                    st.eb(i + 1, i);
                    sel[i + 1] = 1;
                }
            } else {
                now++;
                if(s[i] == '(') {
                    sel[i] = 1;
                } else {
                    sel[i + 1] = 1;
                }
            }
        }
    }
    if(now) goto FAIL;
    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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 70