Submission #660294

#	Time	Username	Problem	Language	Result	Execution time	Memory
660294		berr	Superpozicija (COCI22_superpozicija)	C++17	0 / 110	585 ms	1264 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+37;

int test(string s)
{
    int a=0;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='(') a++;
        else a--;
        if(a<0) return 0;
    }

    if(a) return 0;

    return 1;
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    int t; cin>>t;

    while(t--)
    {

        int n; cin>>n;
        string s; cin>>s;
        vector<array<int, 2>> query(n);

        int flag=1;

        for(int i=0; i<n; i++)
        {
            cin>>query[i][0]>>query[i][1];
            query[i][0]--; query[i][1]--;
            if(query[i][1]!=query[i][0]+1)flag=0;
        }

        if(n%2) cout<<-1<<"\n"; 
        else if(n<=10&&!flag)
        {
            int ans=1e9;
            for(int i=0; i<(1<<n); i++)
            {   
                vector<int> check(n*2);

                for(int l=0; l<n; l++)
                {
                    if((1<<l)&i) check[query[l][1]]=1;
                    else check[query[l][0]]=1;
                }

                string st;

                for(int l=0; l<n*2; l++)
                {
                    if(check[l]) st+=s[l];
                }
                if(test(st)) ans=min(i, ans);
            }

            if(ans==1e9) cout<<-1<<"\n";
            else
            {
                for(int l=0; l<n; l++)
                {
                    if(ans&(1<<l)) cout<<1<<" ";
                    else cout<<0<<" ";
                } 
                cout<<"\n";
            }
        }
       else if(flag)
        {
            vector<pair<array<int, 2>, int>> query2;

            for(int i=0; i<n; i++)
            {
                query2.push_back({query[i], i});
            }

            sort(query2.begin(), query2.end());
            vector<int> d(n);
            int ac=n/2, kap=n/2;
            for(int i=0; i<n; i++)
            {
                if(s[query2[i].first[0]]==s[query2[i].first[1]])
                {
                    d[query2[i].second]=1;
                    if(s[query2[i].first[0]]==')') kap--;
                    else ac--;
                }

            }

            if(ac<0||kap<0) cout<<-1<<"\n";
            else
            {
                for(int i=0; i<n; i++)
                {
                    if(d[query2[i].second]==0)
                    {
                        if(ac>0)
                        {
                            if(s[query2[i].first[0]]==')')
                            d[query2[i].second]=1;
                            else
                            d[query2[i].second]=0;
                            ac--;
                        }
                        else
                        {
                            if(s[query2[i].first[0]]==')')
                            d[query2[i].second]=0;
                            else
                            d[query2[i].second]=1;
                            kap--;
                        }

                    }
                }


                if(ac!=0||kap!=0) cout<<-1<<"\n";
                else
                {
                    string st;
                    vector<int> check(n*2);

                    for(int i=0; i<n; i++)
                    {
                        if(d[i]) check[query[i][1]]=1;
                        else check[query[i][0]]=1;
                    }

                    for(int l=0; l<n*2; l++)
                    {
                        if(check[l]) st+=s[l];
                    }

                    if(test(st))
                    {
                        for(auto i: d) cout<<i<<" ";
                            cout<<"\n";
                    }
                    else cout<<-1<<"\n";

                }           
            } 
        }
        else 
        {
            vector<int> d(n);
            for(int i=0; i<n; i++)
            {
                auto x=query[i];
                if(s[x[0]]==')')
                {
                    if(x[0]<x[1]) d[i]=1;
                }
                if(s[x[0]]==')')
                {
                    if(x[0]>x[1]) d[i]=1;
                }

                               string st;
                vector<int> check(n*2);

                for(int i=0; i<n; i++)
                {
                    if(d[i]) check[query[i][1]]=1;
                    else check[query[i][0]]=1;
                }

                for(int l=0; l<n*2; l++)
                {
                    if(check[l]) st+=s[l];
                }

                if(test(st))
                {
                    for(auto i: d) cout<<i<<" ";
                        cout<<"\n";
                }
                else cout<<-1<<"\n";
            }
        }
    }
}   

Compilation message (stderr)

Main.cpp: In function 'long long int test(std::string)':
Main.cpp:10:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0; i<s.size(); i++)
      |                  ~^~~~~~~~~

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