oj.uz

Submission #1082611

# Submission time Handle Problem Language Result Execution time Memory
1082611 2024-08-31T18:06:45 Z serifefedartar Superpozicija (COCI22_superpozicija) C++17
30 / 110
 54 ms 24620 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
 
#define int long long
int x[MAXN], y[MAXN];
vector<int> L[MAXN], R[MAXN];
 
void solve() {
    int n;
    string S;
    cin >> n >> S;
    S = "#" + S;
 
    map<pair<int,int>,int> mp;
    vector<int> ans(n+1, 0);
    vector<int> active(2*n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        if (S[x[i]] != S[y[i]]) {
            mp[{x[i], y[i]}] = i;
            mp[{y[i], x[i]}] = i;
            R[y[i]].push_back(x[i]);
            L[x[i]].push_back(y[i]);
        }
 
        if (S[x[i]] == '(' && S[y[i]] == '(') {
            ans[i] = 0;
            active[x[i]] = 1;
        } else if (S[x[i]] == ')' && S[y[i]] == ')') {
            ans[i] = 1;
            active[y[i]] = 1;
        } else if (S[x[i]] == '(' && S[y[i]] == ')') {
            ans[i] = 1;
            active[y[i]] = 1;
        } else {
            ans[i] = 0;
            active[x[i]] = 1;
        }
    }
 
    int cnt = 0;
    set<pair<int,int>> completely_left;
    set<pair<int,int>> partially_left;
 
    for (int i = 1; i <= 2*n; i++) {
        for (auto u : L[i])
            partially_left.insert({u, i}); // {i, u}
        for (auto u : R[i]) {
            if (partially_left.count({i, u}) == 0)
                continue;
            completely_left.insert({u, i});
            partially_left.erase({i, u}); // {u, i}
        }
 
        if (active[i]) {
            if (S[i] == '(')
                cnt++;
            else
                cnt--;
        }
 
        if (cnt < 0) {
            if (completely_left.size()) {
 
                int A = mp[*(completely_left.begin())];
                swap(active[x[A]], active[y[A]]);
                ans[A] ^= 1;
                completely_left.erase(completely_left.begin());
                cnt+=2;
 
            } else if (partially_left.size()) {
 
                int A = mp[*(partially_left.begin())];
                swap(active[x[A]], active[y[A]]);
                ans[A] ^= 1;
                partially_left.erase(partially_left.begin());
                cnt++;
 
            } else {
 
                for (int i = 1; i <= n; i++) {
                    R[y[i]].clear();
                    L[x[i]].clear();
                }
 
 
                cout << "-1\n";
                return ;
 
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        R[y[i]].clear();
        L[x[i]].clear();
    }
 
    if (cnt) {
        cout << "-1\n";
        return ;
    }
 
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << "\n";
}
 
signed main() {
    fast;
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11660 KB Output is correct
2 Correct 15 ms 11424 KB Output is correct
3 Correct 15 ms 11656 KB Output is correct
4 Correct 18 ms 13224 KB Output is correct
5 Correct 20 ms 13220 KB Output is correct
6 Correct 11 ms 13140 KB Output is correct
7 Correct 12 ms 13652 KB Output is correct
8 Correct 13 ms 14116 KB Output is correct
9 Correct 14 ms 14664 KB Output is correct
10 Correct 17 ms 15208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 26 ms 10844 KB Output is correct
3 Correct 30 ms 12696 KB Output is correct
4 Correct 31 ms 14452 KB Output is correct
5 Correct 38 ms 16120 KB Output is correct
6 Correct 37 ms 18336 KB Output is correct
7 Correct 19 ms 17752 KB Output is correct
8 Correct 32 ms 20312 KB Output is correct
9 Correct 54 ms 21880 KB Output is correct
10 Correct 50 ms 23612 KB Output is correct
11 Correct 50 ms 24620 KB Output is correct

Subtask #4
0 / 70.0

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