oj.uz

Submission #666894

# Submission time Handle Problem Language Result Execution time Memory
666894 2022-11-29T21:18:01 Z LFFB Superpozicija (COCI22_superpozicija) C++14
10 / 110
 85 ms 3080 KB 
#include <iostream>
#include <string>

#define debug(args...) //printf(args)

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();
        str2.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].first = a;
            pairs[i].second = b;
        }

        if (n < 20) {

            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];

            debug("at i=%d: a=%d, b=%d, c=%c\n", i, a, b, c);

            if (c == '(') {
                str2[std::min(a, b)] = c;
                debug("setting %c at %d\n", c, std::min(a, b));
            }
            if (c == ')') {
                str2[std::max(a, b)] = c;
                debug("setting %c at %d\n", c, std::max(a, b));
            }

        }

        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:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
Main.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
Main.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |             scanf(" %c ", &c);
      |             ~~~~~^~~~~~~~~~~~
Main.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 1216 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 31 ms 1132 KB Output is correct
2 Correct 29 ms 1240 KB Output is correct
3 Correct 25 ms 1492 KB Output is correct
4 Correct 29 ms 1812 KB Output is correct
5 Correct 26 ms 2004 KB Output is correct
6 Correct 18 ms 2204 KB Output is correct
7 Correct 19 ms 2524 KB Output is correct
8 Correct 34 ms 2688 KB Output is correct
9 Correct 28 ms 2968 KB Output is correct
10 Correct 30 ms 3080 KB Output is correct

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