Submission #704975

#	Time	Username	Problem	Language	Result	Execution time	Memory
704975		browntoad	Superpozicija (COCI22_superpozicija)	C++14	0 / 110	18 ms	25916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

const int maxn = 8e5+5;

int n;
string str;
vector<pii> op(maxn);
bool typ = 1;
void inp(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n;
    cin>>str;
    REP(i, n){
        cin>>op[i].f>>op[i].s;
        op[i].f--; op[i].s--;
        if (op[i].s != op[i].f+1) typ = 0;
    }
}
void solve0(){
    assert(0);
    if (n%2){
        cout<<-1<<endl;
        return;
    }
}
void solve1(){
    if (n%2){
        cout<<-1<<endl;
        return;
    }
    vector<int> fans(n);
    int cl = 0, cr = 0;
    REP(i, n){
        assert(op[i].f%2 == 0);
        if (str[op[i].f] == str[op[i].s]){
            if (str[op[i].f] == '('){
                fans[op[i].f/2]=1;
                cl++;
            }
            else {
                fans[op[i].f/2]=-1;
                cr++;
            }
        }
    }
    if (cl>n/2 || cr>n/2){
        cout<<-1<<endl;
        return;
    }
    int cdelt = 0, fail = 0;
    REP(i, n){
        if (fans[i] == 0){
            if (cl < n/2){
                cl++;
                fans[i]=1;
                cdelt++;
            }
            else {
                fans[i]=-1;
                cdelt--;
                cr++;
            }
        }
        else cdelt+=fans[i];
        if (cdelt < 0) fail=1;
    }
    if (cl != n/2 || cr != n/2) fail=1;
    if (fail){
        cout<<-1<<endl;
        return;
    }
    else {
        REP(i, n){
            if (str[op[i].f] == str[op[i].s]) cout<<0;
            else {
                if (fans[op[i].f/2] == (str[op[i].f] == '(')*2-1) cout<<0;
                else cout<<1;
            }
            if (i!=n-1) cout<<' ';
        }
        cout<<endl;
    }

}
signed main(){
    int t; cin>>t;
    while(t--){
        inp();
        if (typ){
            solve1();
        }
        else solve0();
        typ = 1;
    }

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 70