Submission #232922

#	Time	Username	Problem	Language	Result	Execution time	Memory
232922		Saboon	Ili (COI17_ili)	C++14	100 / 100	205 ms	780 KiB

ili

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;

const int maxn = 2e4 + 10;

int n, m;
int a[maxn], b[maxn];
int x[maxn], y[maxn];

int get(string s){
	int sz = s.size();
	int ret = 0;
	if (s[0] == 'c')
		ret += n;
	return ret + stoi(s.substr(1, sz-1));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	string s;
	cin >> s;
	memset(a, -1, sizeof a);
	for (int i = 1; i <= m; i++){
		if (s[i-1] == '1')
			a[i+n] = 1;
		if (s[i-1] == '0')
			a[i+n] = 0;
	}
	for (int i = n+1; i <= n+m; i++){
		string f, s;
		cin >> f >> s;
		x[i] = get(f), y[i] = get(s);
	}
	for (int i = n+m; i >= n+1; i--)
		if (a[i] == 0)
			a[x[i]] = a[y[i]] = 0;
	for (int i = n+1; i <= n+m; i++)
		if (a[x[i]] == 1 or a[y[i]] == 1)
			a[i] = 1;
		else if (a[x[i]] == 0 and a[y[i]] == 0)
			a[i] = 0;
	
	for (int i = n+1; i <= n+m; i++){
		if (a[i] != -1)
			continue;
		for (int j = 1; j <= n; j++){
			if (a[j] == -1)
				b[j] = 1;
			else
				b[j] = a[j];
		}
		for (int j = n+1; j <= n+m; j++)
			b[j] = a[j];
		bool found = 0;
		b[i] = 0;
		for (int j = i; j >= n+1; j--)
			if (b[j] == 0)
				b[x[j]] = b[y[j]] = 0;
		for (int j = n+1; j <= n+m; j++){
			b[j] = (b[x[j]] | b[y[j]]);
			if (a[j] == 1 and b[j] == 0){
				found = 1;
				break;
			}
		}
		if (found){
			a[i] = 1;
			for (int j = i; j <= n+m; j++)
				if (a[x[j]] == 1 or a[y[j]] == 1)
					a[j] = 1;
		}
	}
	for (int i = n+1; i <= n+m; i++)
		if (a[i] == -1)
			cout << '?';
		else
			cout << a[i];
	cout << '\n';
}

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