| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 234759 |
2020-05-25T13:25:42 Z |
ArshiaDadras |
Ili (COI17_ili) |
C++14 |
|
10 ms |
1920 KB |
/* In the name of Allah */
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
vector<int> adj[N];
char c[N], C[N];
bool mark[N];
int n, m;
int read() {
getchar();
char x; int u;
cin >> x >> u;
if (x ^ 'x')
u += n;
return --u;
}
bool go() {
while (true) {
bool flag = false;
for (int u = n + m - 1; u >= n; u--) {
bool ok = true;
for (auto v: adj[u])
ok &= c[v] == '0';
if (ok) {
if (c[u] == '1')
return false;
if (c[u] == '?')
c[u] = '0', flag = true;
}
if (c[u] == '0')
for (auto v: adj[u])
if (c[v] != '0')
c[v] = '0', flag = true;
}
for (int u = n; u < n + m; u++) {
bool ok = false;
for (auto v: adj[u])
ok |= c[v] == '1';
if (ok) {
if (c[u] == '0')
return false;
if (c[u] == '?')
c[u] = '1', flag = true;
}
}
if (!flag)
break;
}
return true;
}
bool check(int u) {
return c[u] = '0', go();
}
void read_input() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> c[n + i];
for (int i = 0; i < m; i++) {
adj[n + i].push_back(read());
adj[n + i].push_back(read());
}
}
void solve() {
for (int u = 0; u < n; u++)
c[u] = '?';
assert(go());
for (int u = 0; u < n + m; u++)
if (c[u] == '?') {
copy(c, c + n + m, C);
if (!check(u))
C[u] = '1';
copy(C, C + n + m, c);
if (c[u] != '?')
assert(go());
}
for (int i = 0; i < m; i++)
cout << c[n + i];
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
read_input(), solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
768 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
768 KB |
Output is correct |
| 5 |
Correct |
5 ms |
768 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
768 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
768 KB |
Output is correct |
| 5 |
Correct |
5 ms |
768 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
768 KB |
Output is correct |
| 8 |
Correct |
7 ms |
768 KB |
Output is correct |
| 9 |
Correct |
9 ms |
768 KB |
Output is correct |
| 10 |
Correct |
8 ms |
768 KB |
Output is correct |
| 11 |
Correct |
10 ms |
896 KB |
Output is correct |
| 12 |
Correct |
7 ms |
896 KB |
Output is correct |
| 13 |
Correct |
7 ms |
768 KB |
Output is correct |
| 14 |
Correct |
8 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
768 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
768 KB |
Output is correct |
| 5 |
Correct |
5 ms |
768 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
768 KB |
Output is correct |
| 8 |
Correct |
7 ms |
768 KB |
Output is correct |
| 9 |
Correct |
9 ms |
768 KB |
Output is correct |
| 10 |
Correct |
8 ms |
768 KB |
Output is correct |
| 11 |
Correct |
10 ms |
896 KB |
Output is correct |
| 12 |
Correct |
7 ms |
896 KB |
Output is correct |
| 13 |
Correct |
7 ms |
768 KB |
Output is correct |
| 14 |
Correct |
8 ms |
896 KB |
Output is correct |
| 15 |
Runtime error |
7 ms |
1920 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Halted |
0 ms |
0 KB |
- |
