Submission #666819

#	Time	Username	Problem	Language	Result	Execution time	Memory
666819		mmk	Superpozicija (COCI22_superpozicija)	C++17	0 / 110	1087 ms	616 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
int marc[MAXN*2];
int par[MAXN*2];
int n;
string s;
bool encerrou = false;
bool check()
{
    int q = 0;
    bool aux = false;
    for(int i = 0; i < 2*n; i++)
    {
        if(marc[i] == 1)
        {
            aux = true;
            if(s[i] == '(') q++;
            else if(q == 0)
            {
                q = - 9;
                aux = false;
            }
            else q--;
        }
    }
    if(q == 0 && aux)
        return true;
    else return false;
}
void bt(int id)
{
    if(encerrou) return;
    if(id == n*2)
    {
        if(check())
        {
            for(int i = 0; i < 2*n; i++)
            {
                if(marc[i] == 1)
                {
                    if(par[i] > i)
                        cout << "0 ";
                    else
                        cout << "1 ";
                }
            }
            encerrou = true;
        }
        return;
    }
    if(marc[id] == -1)
    {
        bt(id+1);
        return;
    }
    marc[id] = 1;
    marc[par[id]] = -1;
    bt(id+1);
    marc[id] = -1;
    marc[par[id]] = 1;
    bt(id+1);
}
int main()
{
        cin.tie(0)->sync_with_stdio(0);
        int t;
        cin >> t;
        while(t--)
        {
            cin >> n;
            cin >> s;
            for(int i = 0; i < n; i++)
            {
                int a,b;
                cin >> a >> b;
                a--;
                b--;
                par[a] = b;
                par[b] = a;
            }
            bt(0);
            if(!encerrou) cout << "-1";
            for(int i = 0; i < 2*n; i++)
            {
                par[i] = 0;
                marc[i] = 0;
            }
            encerrou = false;
            cout << "\n";
        }
}

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