oj.uz

Submission #704984

# Submission time Handle Problem Language Result Execution time Memory
704984 2023-03-03T07:36:16 Z PixelCat Superpozicija (COCI22_superpozicija) C++14
10 / 110
 297 ms 4612 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200010;

char s[MAXN];
char t[MAXN];
int sel[MAXN];

void solve(int n, vector<pii> &p) {
    vector<int> st;
    int now = 0;
    if(n % 2) goto FAIL;
    for(int i = 2; i <= n * 2; i += 2) {
        if(s[i] == s[i - 1]) {
            t[i / 2] = s[i];
        } else {
            t[i / 2] = '.';
        }
    }
    For(i, 1, n) {
        if(t[i] == '(') {
            now++;
        } else if(t[i] == ')') {
            now--;
            if(now < 0) {
                if(!sz(st)) goto FAIL;
                t[st.back()] = '(';
                st.pop_back();
                now += 2;
            }
        } else {
            if(now > 0) {
                now--;
                t[i] = ')';
                st.eb(i);
            } else {
                now++;
                t[i] = '(';
            }
        }
    }
    // For(i, 1, n) cout << t[i];
    // cout << "\n";
    if(now) goto FAIL;
    For(i, 0, n - 1) {
        auto it = p[i];
        if(t[it.S / 2] == s[it.F]) cout << "0";
        else cout << "1";
        cout << " \n"[i == n - 1];
    }
    return;
    FAIL:
    cout << "-1\n";
    return;
}

bool solve2(int n, vector<pii> p) {
    for(auto &i:p) {
        if(s[i.F] != s[i.S]) return false;
        if(s[i.F] == '(') sel[i.F] = 1;
        else sel[i.S] = 1;
    }
    int now = 0;
    bool ac = true;
    For(i, 1, n * 2) if(sel[i]) {
        if(s[i] == '(') now++;
        else now--;
        if(now < 0) ac = false;
    }
    if(!ac || now != 0) cout << "-1\n";
    else {
        For(i, 0, n - 1) {
            auto x = p[i];
            if(sel[x.F]) cout << "0";
            else cout << "1";
            cout << " \n"[i == n - 1];
        }
    }
    return true;
}

bool solve3(int n, vector<pii> p) {
    if(n > 10) return false;
    For(mask, 0, (1 << n) - 1) {
        fill(sel, sel + 100, 0);
        For(i, 0, n - 1) {
            if(mask & (1 << i)) {
                sel[p[i].F] = 1;
            } else {
                sel[p[i].S] = 1;
            }
        }
        bool ok = true;
        int now = 0;
        For(i, 1, n * 2) if(sel[i]) {
            if(s[i] == '(') now++;
            else now--;
            if(now < 0) ok = false;
        }
        if(ok && now == 0) {
            For(i, 0, n - 1) {
                if(mask & (1 << i)) cout << "0";
                else cout << "1";
                cout << " \n"[i == n - 1];
            }
            return true;
        }
    }
    cout << "-1\n";
    return true;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nya ><
    int N; cin >> N;
    while(N--) {
        int n; cin >> n;
        For(i, 1, n * 2) sel[i] = 0;
        cin >> (s + 1);
        vector<pii> p(n);
        for(auto &i:p) {
            cin >> i.F >> i.S;
        }
        // solve(n, p);
        assert(solve2(n, p) || solve3(n, p));
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 388 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 22 ms 340 KB Output is correct
2 Correct 15 ms 812 KB Output is correct
3 Correct 16 ms 1256 KB Output is correct
4 Correct 18 ms 1784 KB Output is correct
5 Correct 14 ms 2220 KB Output is correct
6 Correct 9 ms 2780 KB Output is correct
7 Correct 12 ms 3284 KB Output is correct
8 Correct 15 ms 3700 KB Output is correct
9 Correct 24 ms 4180 KB Output is correct
10 Correct 27 ms 4612 KB Output is correct

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 297 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -