This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
string v;
cin >> v;
vector<vector<int>> g(n + m);
for (int i = 0; i < m; i++) {
for (int itr = 0; itr < 2; itr++) {
char c;
int from;
cin >> c >> from;
--from;
if (c == 'x') {
from += m;
}
g[from].push_back(i);
}
}
vector<vector<int>> sols;
for (int i = 0; i < (1 << n); i++) {
vector<int> que(n);
vector<int> a(n + m, 0);
vector<int> inDeg(n + m, 2);
for (int j = 0; j < n; j++) {
que[j] = j + m;
a[j + m] = !!(i & (1 << j));
inDeg[j + m] = 0;
}
for (int b = 0; b < (int) que.size(); b++) {
int f = que[b];
for (int u : g[f]) {
inDeg[u] -= 1;
a[u] |= a[f];
if (inDeg[u] == 0) {
que.push_back(u);
}
}
}
bool can = true;
for (int j = 0; j < m; j++) {
if (v[j] == '?') {
continue;
}
if ((v[j] - '0') != a[j]) {
can = false;
break;
}
}
if (can) {
sols.emplace_back(a);
}
}
vector<set<int>> se(m);
for (const auto& a : sols) {
for (int i = 0; i < m; i++) {
se[i].insert(a[i]);
}
}
for (int i = 0; i < m; i++) {
if (se[i].size() == 1) {
cout << *se[i].begin();
} else {
cout << '?';
}
}
cout << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |