oj.uz

Submission #232157

# Submission time Handle Problem Language Result Execution time Memory
232157 2020-05-16T09:56:51 Z TempoTemp Ili (COI17_ili) C++14
100 / 100
 2289 ms 888 KB 
// I don't know ..
#include<bits/stdc++.h>
using namespace std;
const int N = 20004;
int n, m, A[N], B[N], R[N], F[N];
string S, T;
inline bool Check()
{
    for (int i = 1; i <= m; i ++)
        F[i] = R[i];
    for (int i = 1; i <= n; i ++)
        F[i + m] = -1;
    for (int i = m; i; i --)
        if (F[i] == 0)
        {
            if (F[A[i]] == 1 || F[B[i]] == 1)
                return 0;
            F[A[i]] = F[B[i]] = 0;
        }
    for (int i = 1; i <= m; i ++)
        if (F[A[i]] == 0 && F[B[i]] == 0)
        {
            if (F[i] == 1)
                return 0;
            F[i] = 0;
        }
    for (int i = 1; i <= m; i ++)
        if (F[A[i]] == 1 || F[B[i]] == 1)
        {
            if (F[i] == 0)
                return 0;
            F[i] = 1;
        }
    for (int i = m; i; i --)
        if (F[i] == 1)
        {
            if (F[A[i]] == 0 && F[B[i]] == 0)
                return 0;
            if (F[A[i]] == 0)
                F[B[i]] = 1;
            else if (F[B[i]] == 0)
                F[A[i]] = 1;
        }
    return 1;
}
int main()
{
    cin >> n >> m >> S;
    S = "#" + S;
    memset(R, -1, sizeof(R));
    for (int i = 1; i <= m; i ++)
        if (S[i] != '?')
            R[i] = S[i] - '0';
    for (int i = 1; i <= m; i ++)
    {
        char ch1, ch2;
        cin >> ch1 >> A[i] >> ch2 >> B[i];
        if (ch1 == 'x') A[i] += m;
        if (ch2 == 'x') B[i] += m;
    }
    for (int i = 1; i <= m; i ++)
        if (S[i] != '?')
            T += S[i];
        else
        {
            int ff = 0;
            R[i] = 0;
            if (Check())
                ff |= 1;
            R[i] = 1;
            if (Check())
                ff |= 2;
            if (ff == 3)
                T += "?", R[i] = -1;
            else if (ff == 1)
                T += "0", R[i] = 0;
            else
                T += "1", R[i] = 1;
            R[i] = -1;
        }
    cout << T << "\n";
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 416 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 8 ms 436 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 416 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 8 ms 436 KB Output is correct
15 Correct 639 ms 632 KB Output is correct
16 Correct 1235 ms 760 KB Output is correct
17 Correct 1488 ms 680 KB Output is correct
18 Correct 2156 ms 884 KB Output is correct
19 Correct 1256 ms 760 KB Output is correct
20 Correct 2289 ms 736 KB Output is correct
21 Correct 2191 ms 764 KB Output is correct
22 Correct 381 ms 760 KB Output is correct
23 Correct 420 ms 760 KB Output is correct
24 Correct 411 ms 760 KB Output is correct
25 Correct 574 ms 760 KB Output is correct
26 Correct 572 ms 760 KB Output is correct
27 Correct 536 ms 760 KB Output is correct
28 Correct 525 ms 764 KB Output is correct
29 Correct 542 ms 888 KB Output is correct
30 Correct 562 ms 764 KB Output is correct
31 Correct 608 ms 760 KB Output is correct
32 Correct 661 ms 764 KB Output is correct