Submission #144945

#	Time	Username	Problem	Language	Result	Execution time	Memory
144945		LeMur	Ili (COI17_ili)	C++14	100 / 100	581 ms	13404 KiB

ili

////////////////////////////////////////////    _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 10005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;

int n , m;
string s;

bitset <N> mas[N];
bitset <N> A;
vector <int> vec;

vector <int> g;
vector < pair<char,int> > gg[N];

int C[N] , X[N];

bool check(int id){
    for(int i=0;i<n;i++){
        if(mas[id][i])
            X[i] = 0;
        else
            X[i] = A[i] ^ 1;
    }
    for(int i=0;i<m;i++){
        int a = (gg[i][0].first == 'c') ? C[ gg[i][0].second ] : X[ gg[i][0].second ];
        int b = (gg[i][1].first == 'c') ? C[ gg[i][1].second ] : X[ gg[i][1].second ];
        C[i] = (a | b);
        if(s[i] == '1' && C[i] == 0)return true;
    }
    return false;
}

int main(){
	mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> m;
    cin >> s;
    for(int i=0;i<m;i++){
        char c1 , c2;
        int x1 , x2;
        cin >> c1 >> x1;
        cin >> c2 >> x2;
        --x1;
        --x2;
        if(c1 == 'x')
            mas[i][x1] = '1';
        else
            mas[i] |= mas[x1];
        if(c2 == 'x')
            mas[i][x2] = '1';
        else
            mas[i] |= mas[x2];

        gg[i].push_back(make_pair(c1 , x1));
        gg[i].push_back(make_pair(c2 , x2));

        if(s[i] == '0'){
            A |= mas[i];
        }
        if(s[i] == '1'){
            vec.push_back(i);
        }
    }
    for(int i=0;i<n;i++){
        if(A[i] == 1){
            for(int j=0;j<m;j++){
                mas[j][i] = 0;
            }
        }
    }
    for(int j=0;j<m;j++){
        if(mas[j].count() == 0){
            s[j] = '0';
        }
    }
    for(int i=0;i<m;i++){
        if(s[i] == '?'){
            if(check(i)){
                s[i] = '1';
            }
        }
    }
    cout << s << endl;
    return 0;
}

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