Submission #666856

#TimeUsernameProblemLanguageResultExecution timeMemory
666856LFFBSuperpozicija (COCI22_superpozicija)C++14
0 / 110
92 ms1212 KiB
#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 (stderr)

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);
      |             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...