oj.uz

Submission #666856

# Submission time Handle Problem Language Result Execution time Memory
666856 2022-11-29T19:44:46 Z LFFB Superpozicija (COCI22_superpozicija) C++14
0 / 110
 92 ms 1212 KB 
#include <iostream>
#include <string>

const int MAX_N = 1e5 + 10;

template<typename T>
class SpecialVector {
private:
    T* values;
    T standard;
    int* lastChanged;
    int time;
public:
    SpecialVector(int size, T s) {
        values = new T[size];
        lastChanged = new int[size];
        standard = s;
        time = 1;
    }
    T& operator[](int i) {
        if (lastChanged[i] != time) {
            lastChanged[i] = time;
            values[i] = standard;
        }
        return values[i];
    }
    void clear() {
        time++;
    }
};

int n, t;

SpecialVector<char> str(2*MAX_N, ' ');
SpecialVector<char> str2(2*MAX_N, ' ');
SpecialVector<std::pair<int, int>> pairs(MAX_N, {0, 0});

bool verifyStr2() {
    int verify = 0;
    for (int i = 0; i < 2*n; i++) {
        if (str2[i] == '(') {
            verify++;
        } else if (str2[i] == ')') {
            verify--;
            if (verify < 0) return false;
        }
    }
    if (verify != 0) return false;
    return true;
}

bool brute(int i) {

    if (i == -1) {
        bool valid = verifyStr2();
        return valid;
    }

    int a = pairs[i].first;
    int b = pairs[i].second;
    bool correct;

    str2[a] = str[a];
    correct = brute(i - 1);
    str2[a] = ' ';

    if (correct) {
        printf("0");
        if (i != n - 1) printf(" ");
        return true;
    }

    str2[b] = str[b];
    correct = brute(i - 1);
    str2[b] = ' ';

    if (correct) {
        printf("1");
        if (i != n - 1) printf(" ");
        return true;
    }

    return false;

}

int main() {
    scanf("%d", &t);
    for (int test = 0; test < t; test++) {

        str.clear();
        pairs.clear();

        scanf("%d", &n);

        int count1 = 0;
        int count2 = 0;

        for (int i = 0; i < 2*n; i++) {
            char c;
            scanf(" %c ", &c);
            str[i] = c;
            if (c == '(') count1++;
            if (c == ')') count2++;
        }

        for (int i = 0; i < n; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            a--; b--;
            pairs[i] = {a, b};
        }

        if (n < 15) {

            bool found = brute(n - 1);
            if (!found) printf("-1");
            printf("\n");

            continue;
        }

        for (int i = 0; i < n; i++) {

            int a = pairs[i].first;
            int b = pairs[i].second;
            char c = str[a];

            if (c == '(') str2[std::min(a, b)] = c;
            if (c == ')') str2[std::max(a, b)] = c;

        }

        bool valid = verifyStr2();
        if (!valid) {
            printf("-1\n");
            continue;
        }

        for (int i = 0; i < n; i++) {

            int a = pairs[i].first;
            int b = pairs[i].second;
            char c = str[a];

            if (c == '(') {
                printf("%d", a < b ? 0 : 1);
            } else {
                printf("%d", a < b ? 1 : 0);
            }
            if (i != n - 1) printf(" ");
        }
        printf("\n");

    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
Main.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
Main.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |             scanf(" %c ", &c);
      |             ~~~~~^~~~~~~~~~~~
Main.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 70.0

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