| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40194 |
2018-01-29T12:00:06 Z |
krauch |
Ili (COI17_ili) |
C++14 |
|
2749 ms |
2092 KB |
/*
_ _ _______ _ _
| | / / | _____| | | / /
| | / / | | | | / /
| |/ / | |_____ | |/ /
| |\ \ | _____| | |\ \
| | \ \ | | | | \ \
| | \ \ | |_____ | | \ \
|_| \_\ |_______| |_| \_\
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek
#define fname ""
const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 705;
int n, m, a[N], b[N];
bitset < N > bit[N];
int main() {
//ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef krauch
freopen("input.txt", "r", stdin);
#else
//freopen(fname".in", "r", stdin);
//freopen(fname".out", "w", stdout);
#endif
scanf("%d %d\n", &n, &m);
forn(i, 1, n) b[i] = -1;
forn(i, 1, m) {
char c;
scanf("%c", &c);
if (c == '?') a[i] = -1;
else a[i] = c - '0';
}
scanf("\n");
forn(i, 1, m) {
char c;
int x1 = -1, x2 = -1, x;
scanf("%c%d ", &c, &x);
if (c == 'x') {
bit[i][x] = 1;
}
else {
bit[i] |= bit[x];
x1 = a[x];
}
scanf("%c%d\n", &c, &x);
if (c == 'x') {
bit[i][x] = 1;
}
else {
bit[i] |= bit[x];
x2 = a[x];
}
if (x1 != -1 && x2 != -1) a[i] = (x1 | x2);
if (a[i] == 0) {
forn(j, 1, n) if (bit[i][j] == 1) b[j] = 0;
}
}
forn(l, 1, max(n, m) + 1) {
forn(i, 1, m) {
int cnt = 0;
forn(j, 1, n) if (bit[i][j] == 1) cnt += (b[j] == 0);
if (cnt == bit[i].count()) a[i] = 0;
}
forn(i, 1, m) {
int cnt = 0;
forn(j, 1, n) if (bit[i][j] == 1) cnt += (b[j] == 0);
if (cnt == bit[i].count() - 1 && a[i] == 1) forn(j, 1, n) if (bit[i][j] == 1 && b[j] != 0) b[j] = 1;
}
forn(i, 1, m) {
forn(j, 1, n) {
if (bit[i][j] == 1 && b[j] == 1) a[i] = 1;
}
}
forn(i, 1, m) {
if (a[i] != -1) continue;
forn(j, 1, m) {
if (a[j] != 1) continue;
if (bit[i].count() == (bit[i] | bit[j]).count()) {
a[i] = 1;
break;
}
}
}
forn(i, 1, m) {
forn(j, 1, n) {
if (bit[i][j] == 1 && b[j] == 0) bit[i][j] = 0;
}
}
}
forn(i, 1, m) {
if (a[i] == -1) cout << "?";
else cout << a[i];
}
cout << "\n";
return 0;
}
Compilation message
ili.cpp: In function 'int main()':
ili.cpp:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cnt == bit[i].count()) a[i] = 0;
^
ili.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cnt == bit[i].count() - 1 && a[i] == 1) forn(j, 1, n) if (bit[i][j] == 1 && b[j] != 0) b[j] = 1;
^
ili.cpp:57:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d\n", &n, &m);
^
ili.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &c);
^
ili.cpp:65:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n");
^
ili.cpp:69:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c%d ", &c, &x);
^
ili.cpp:77:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c%d\n", &c, &x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2092 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2092 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 8 |
Correct |
2092 ms |
2092 KB |
Output is correct |
| 9 |
Correct |
1111 ms |
2092 KB |
Output is correct |
| 10 |
Correct |
1574 ms |
2092 KB |
Output is correct |
| 11 |
Correct |
2501 ms |
2092 KB |
Output is correct |
| 12 |
Correct |
811 ms |
2092 KB |
Output is correct |
| 13 |
Correct |
1008 ms |
2092 KB |
Output is correct |
| 14 |
Correct |
2749 ms |
2092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2092 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 8 |
Correct |
2092 ms |
2092 KB |
Output is correct |
| 9 |
Correct |
1111 ms |
2092 KB |
Output is correct |
| 10 |
Correct |
1574 ms |
2092 KB |
Output is correct |
| 11 |
Correct |
2501 ms |
2092 KB |
Output is correct |
| 12 |
Correct |
811 ms |
2092 KB |
Output is correct |
| 13 |
Correct |
1008 ms |
2092 KB |
Output is correct |
| 14 |
Correct |
2749 ms |
2092 KB |
Output is correct |
| 15 |
Incorrect |
0 ms |
2092 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
