oj.uz

Submission #666819

# Submission time Handle Problem Language Result Execution time Memory
666819 2022-11-29T18:53:36 Z mmk Superpozicija (COCI22_superpozicija) C++17
0 / 110
 1000 ms 616 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 351 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 351 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -