oj.uz

Submission #667391

# Submission time Handle Problem Language Result Execution time Memory
667391 2022-12-01T08:50:36 Z neki Superpozicija (COCI22_superpozicija) C++14
0 / 110
 65 ms 1068 KB 
#include <bits/stdc++.h>
#define ll long long
#define vc vector

using namespace std;

int main() {
    ll tcs;cin >> tcs;
    while(tcs--){
        ll n; cin >>n;
        string s;cin >> s;
        vc<vc<ll>> dod(2 * n);
        vc<ll> p(2 * n), ans(n), a(n), b(n);
        for(ll i = 0; i < n; ++i){
            cin >> a[i] >> b[i];--a[i], --b[i];assert(a[i] < b[i]);
                 if(s[a[i]]=='(' && s[b[i]]==')') ans[i]=1, dod[a[i]].push_back(i), dod[b[i]].push_back(i), --p[b[i]];
            else if(s[a[i]]==')' && s[b[i]]=='(') ans[i]=0, dod[a[i]].push_back(i), dod[b[i]].push_back(i), --p[a[i]];
            else if(s[a[i]]=='(' && s[b[i]]=='(') ans[i]=0, ++p[a[i]];
            else if(s[a[i]]==')' && s[b[i]]==')') ans[i]=1, --p[b[i]];
            else assert(0);
        }
        vc<ll> d[3];
        vc<ll> st(n, 0);
        ll br=1, cur;
        for(ll i=0;br && i<2 * n;++i){
            cur+=p[i];
            for(auto v: dod[i])if(st[v]!=-1){
                ++st[v];
                assert(st[v]==1 or st[v]==2);
                d[st[v]].push_back(v);
            }
            while(cur<0){
                ll nasu=0;
                while(!nasu && d[2].size()){
                    ll u=d[2].back();
                    assert(0<=u && u<n);
                    assert(st[u]!=-1);
                    st[u]=-1;
                    ans[u]=!ans[u];
                    cur+=2;
                    nasu=1;
                    assert(d[2].size());
                    d[2].pop_back();
                }
                while(!nasu && d[1].size()){
                    ll u=d[1].back();
                    assert(0<=u && u<n);
                    assert(st[u]==1);
                    if(st[u]!=-1){
                        st[u]=-1;
                        ans[u]=!ans[u];
                        cur+=1; p[(ans[u])? b[u]:a[u]]+=1;
                        nasu=1;
                    }
                    assert(d[1].size());
                    d[1].pop_back();
                }
                if(!nasu) {br=0; break;}
            }
        }
        if(br && cur==0){
            for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
        }
        else cout << - 1 << endl;
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:62:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   62 |             for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
      |             ^~~
Main.cpp:62:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   62 |             for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
      |                                                       ^~~~
Main.cpp:61:9: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |         if(br && cur==0){
      |         ^~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 65 ms 1036 KB Output isn't correct
2 Halted 0 ms 0 KB -