oj.uz

Submission #40197

# Submission time Handle Problem Language Result Execution time Memory
40197 2018-01-29T12:56:25 Z krauch Ili (COI17_ili) C++14
7 / 100
 4000 ms 14364 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 = 10000;

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(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(l, 1, max(n, m) + 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:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (cnt == bit[i].count()) a[i] = 0;
                     ^
ili.cpp:100: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);
                                ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 14364 KB Output is correct
2 Correct 0 ms 14364 KB Output is correct
3 Correct 2 ms 14364 KB Output is correct
4 Correct 0 ms 14364 KB Output is correct
5 Correct 3 ms 14364 KB Output is correct
6 Correct 0 ms 14364 KB Output is correct
7 Correct 0 ms 14364 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 14364 KB Output is correct
2 Correct 0 ms 14364 KB Output is correct
3 Correct 2 ms 14364 KB Output is correct
4 Correct 0 ms 14364 KB Output is correct
5 Correct 3 ms 14364 KB Output is correct
6 Correct 0 ms 14364 KB Output is correct
7 Correct 0 ms 14364 KB Output is correct
8 Execution timed out 4000 ms 14364 KB Execution timed out
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 14364 KB Output is correct
2 Correct 0 ms 14364 KB Output is correct
3 Correct 2 ms 14364 KB Output is correct
4 Correct 0 ms 14364 KB Output is correct
5 Correct 3 ms 14364 KB Output is correct
6 Correct 0 ms 14364 KB Output is correct
7 Correct 0 ms 14364 KB Output is correct
8 Execution timed out 4000 ms 14364 KB Execution timed out
9 Halted 0 ms 0 KB -