Submission #374556

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
374556	2021-03-07T12:51:39 Z	Return_0	Ili (COI17_ili)	C++17	49 / 100	4000 ms	12908 KB

ili

#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

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

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 1e4 + 1;

bitset <N> bt [N], lmp, mask;
ll X [N], Y [N], n, m;
char state [N], ans [N];
vector <ll> ones;

bool ok () {
	for (auto &v : ones) if (!(lmp & bt[v]).count()) return false;
	return true;
}

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

	cin>> n >> m;
	for (ll i = 1; i <= n; i++) mask[i] = 1;
	for (ll i = 1; i <= m; i++) {
		cin>> state[i];
		if (state[i] == '1') ones.push_back(i);
	}

	for (ll i = 1; i <= m; i++) {
		char c;
		cin>> c;
		if (c == 'x') {
			cin>> X[i];
			bt[i][X[i]] = 1;
		} else {
			cin>> X[i];
			bt[i] |= bt[X[i]];
			X[i] += N;
		}

		cin>> c;
		if (c == 'x') {
			cin>> Y[i];
			bt[i][Y[i]] = 1;
		} else {
			cin>> Y[i];
			bt[i] |= bt[Y[i]];
			Y[i] += N;
		}
	}

	lmp = mask;
	for (ll i = 1; i <= m; i++) {
		if (state[i] == '0') {
			ans[i] = '0';
			bt[i].flip();
			lmp &= bt[i];
		}

		else if (state[i] == '1') ans[i] = '1';
	}

	mask = lmp;
	for (ll i = 1; i <= m; i++) if (state[i] == '?') {
		if (!(lmp & bt[i]).count()) ans[i] = '0';
		else {
			bt[i].flip();
			lmp &= bt[i];
			if (!ok()) ans[i] = '1';
			else ans[i] = '?';
			lmp = mask;
		}
	}

	for (ll i = 1; i <= m; i++) cout<< ans[i];

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
4 4
10??
x1 x2
x2 x3
x3 x4
x1 c3

4 5
11???
x1 x2
x3 x4
x1 x3
x2 x4
c3 c4

*/

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct

Subtask #2

42.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	4 ms	1004 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	3 ms	876 KB	Output is correct
11	Correct	3 ms	1004 KB	Output is correct
12	Correct	2 ms	876 KB	Output is correct
13	Correct	3 ms	1004 KB	Output is correct
14	Correct	3 ms	1004 KB	Output is correct

Subtask #3

0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	4 ms	1004 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	3 ms	876 KB	Output is correct
11	Correct	3 ms	1004 KB	Output is correct
12	Correct	2 ms	876 KB	Output is correct
13	Correct	3 ms	1004 KB	Output is correct
14	Correct	3 ms	1004 KB	Output is correct
15	Correct	80 ms	7884 KB	Output is correct
16	Correct	323 ms	9068 KB	Output is correct
17	Correct	246 ms	10860 KB	Output is correct
18	Correct	1136 ms	12780 KB	Output is correct
19	Correct	446 ms	9196 KB	Output is correct
20	Correct	1311 ms	12648 KB	Output is correct
21	Correct	2834 ms	12908 KB	Output is correct
22	Correct	2796 ms	12416 KB	Output is correct
23	Correct	3084 ms	12752 KB	Output is correct
24	Correct	2891 ms	12728 KB	Output is correct
25	Execution timed out	4058 ms	12652 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-