Submission #144930

#	Time	Username	Problem	Language	Result	Execution time	Memory
144930		LeMur	Ili (COI17_ili)	C++14	49 / 100	4102 ms	12824 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;
int cnt[N];

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];

        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++){
        cnt[j] = mas[j].count();
        if(mas[j].count() == 0){
            s[j] = '0';
        }
    }
    for(int i=0;i<m;i++){
        if(s[i] == '?'){
            for(int j=0;j<(int)vec.size();j++){
                int id = vec[j];
                if(cnt[i] < cnt[id])continue;
                if((mas[i] & mas[id]) == mas[id]){
                    s[i] = '1';
                    break;
                }
            }
        }
    }
    cout << s << endl;
    return 0;
}

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