Submission #545278

#	Time	Username	Problem	Language	Result	Execution time	Memory
545278		tranxuanbach	Ili (COI17_ili)	C++17	100 / 100	639 ms	436 KiB

ili

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

const int N = 1e4 + 5;

int n, m;
char a[N];
int b[N][2];

bool val[2 * N];
char ans[N];

void dime(){
    FordE(i, m + n, 1 + n){
        if (val[i] == 0){
            val[b[i - n][0]] = val[b[i - n][1]] = 0;
        }
    }
    ForE(i, 1 + n, m + n){
        val[i] = val[b[i - n][0]] | val[b[i - n][1]];
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m;
    ForE(i, 1, m){
        cin >> a[i];
    }
    ForE(i, 1, m){
        ForE(j, 0, 1){
            char type; cin >> type; int u; cin >> u;
            if (type == 'c'){
                u += n;
            }
            b[i][j] = u;
        }
    }

    ForE(i, 1, m){
        ans[i] = '?';
    }
    ForE(i, 1, n + m){
        val[i] = 1;
    }
    ForE(i, 1, m){
        if (a[i] != '?'){
            ans[i] = a[i];
            if (ans[i] == '0'){
                val[i + n] = 0;
            }
        }
    }
    dime();
    ForE(i, 1 + n, m + n){
        if (val[i] == 0){
            ans[i - n] = '0';
        }
    }
    ForE(i, 1, m){
        if (ans[i] == '?'){
            ForE(j, 1, n + m){
                val[j] = 1;
            }
            ForE(j, 1, m){
                if (j == i or ans[j] == '0'){
                    val[j + n] = 0;
                }
            }
            dime();
            bool ck = 1;
            ForE(j, 1, m){
                if (ans[j] != '?' and val[j + n] != ans[j] - '0'){
                    ck = 0;
                    break;
                }
            }
            if (!ck){
                ans[i] = '1';
            }
        }
    }
    ForE(i, 1, m){
        cout << ans[i];
    } cout << endl;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51