Submission #232861

#	Time	Username	Problem	Language	Result	Execution time	Memory
232861		shayan_p	Ili (COI17_ili)	C++14	49 / 100	4086 ms	13196 KiB

ili

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e4 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

bitset<maxn> bs[maxn], zr, tmp;
vector<int> to[maxn];

int toInt(string s){
    stringstream ss;
    ss << s;
    int x;
    ss >> x;
    return x;
}
void inp(int i){
    string s;
    cin >> s;
    if(s[0] == 'c')
	bs[i] = bs[i] | bs[toInt(s.substr(1))-1], to[toInt(s.substr(1))-1].PB(i);
    else
	bs[i][toInt(s.substr(1))-1] = 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    for(int i = 0; i < m; i++){
	inp(i), inp(i);	
    }
    for(int i = 0; i < m; i++){
	if(s[i] == '0')
	    zr|= bs[i];
    }
    for(int i = 0; i < m; i++){
	tmp = zr & bs[i];
	if(tmp == bs[i])
	    s[i] = '0';
	bs[i] = bs[i] ^ tmp;
    }
    for(int i = 0; i < m; i++){
	bool bad = 0;
	if(s[i] == '?'){
	    for(int j = m-1; j >= 0; j--){
		bad|= (s[j] == '1' && (bs[i] & bs[j]) == bs[j]);
		if(bad)
		    break;
	    }
	    if(bad)
		s[i] = '!';
	}	
	if(s[i] == '1' || s[i] == '!')
	    for(int j : to[i]){
		if(s[j] == '?')
		    s[j] = '!';
	    }
    }
    for(int i = 0; i < m; i++){
	if(s[i] == '!')
	    s[i] = '1';
    }
    return cout << s << endl, 0;
}

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