Submission #667466

#	Time	Username	Problem	Language	Result	Execution time	Memory
667466		neki	Superpozicija (COCI22_superpozicija)	C++14	110 / 110	92 ms	14404 KiB

Main

#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];
                 if(s[a[i]]=='(' && s[b[i]]==')') ans[i]=1, dod[a[i]].push_back(i), --p[b[i]];
            else if(s[a[i]]==')' && s[b[i]]=='(') ans[i]=0, dod[a[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);
        }
        ll br=1, cur=0;
        map<ll, ll> d;
        for(ll i=0;br && i<2 * n;++i){
            cur+=p[i];
            for(auto v: dod[i]) d[b[v]]=v;
            while(cur<0){
                if(d.size()){
                    auto t=(*d.begin()).second; d.erase(d.begin());
                    if(a[t]<=i)++cur;
                    else assert(0);
                    if(b[t]<=i)++cur;
                    else ++p[b[t]];
                    ans[t]=!ans[t];
                }
                else{br=0;break;}
            }
        }
        if(br && cur==0){
            for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
            vc<ll> vz(2 * n, 0);
            //for(ll i=0;i<n;++i) vz[(ans[i])?b[i]:a[i]]=1;
            //for(ll i=0;i<2 *n;++i) if(vz[i]) cout << s[i];cout <<endl;
        }
        else cout << - 1 << endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |             for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
      |             ^~~
Main.cpp:40:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |             for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
      |                                                       ^~~~

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