제출 #704957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704957		PixelCat	Superpozicija (COCI22_superpozicija)	C++14	0 / 110	17 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];
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;
        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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 70