Submission #666894

#	Time	Username	Problem	Language	Result	Execution time	Memory
666894		LFFB	Superpozicija (COCI22_superpozicija)	C++14	10 / 110	85 ms	3080 KiB

Main

#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 (stderr)

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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 70