Submission #232157

#	Time	Username	Problem	Language	Result	Execution time	Memory
232157		TempoTemp	Ili (COI17_ili)	C++14	100 / 100	2289 ms	888 KiB

ili

// 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 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51