Submission #370209

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370209	2021-02-23T15:06:11 Z	soroush	Ili (COI17_ili)	C++17	49 / 100	4000 ms	12652 KB

ili

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e4 + 10;

#define pb push_back
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
#define dokme(x) cout << x, exit(0);

int n , m;
string s;

char c[maxn][2];
int a[maxn][2];
vector < int > ans[2];

bitset < maxn > x[maxn] , zero;

bool chk(int pos){
	x[pos].flip();
	for(int i : ans[1]){
		bool ok = 0;
		for(int j = x[pos]._Find_first() ; j < maxn ; j = x[pos]._Find_next(j))
			if(x[i][j]){
				ok = 1;
				break;
			}
		if(!ok)return(0);
	}
	return(1);
}

int32_t main(){
	migmig;
	cin >> n >> m >> s;
	s = "6" + s;
	for(int i = 1 ; i <= m ; i ++){
		for(int j = 0 ; j < 2 ; j ++){
			cin >> c[i][j] >> a[i][j] , a[i][j] += ((c[i][j] == 'c') ? n : 0);
			if(a[i][j] <= n)x[i][a[i][j]] = 1;
			else
				for(int v = x[a[i][j] - n]._Find_first() ; v < maxn ; v = x[a[i][j] - n]._Find_next(v))
					x[i][v] = 1;
		}
		if(s[i] == '0')ans[0].pb(i);
		if(s[i] == '1')ans[1].pb(i);
	}
	for(int i : ans[0])
		zero |= x[i];
	for(int i = 1 ; i <= m ; i ++){
		x[i] ^= (zero & x[i]);
		if(x[i].count() == 0 and s[i] == '?')
			s[i] = '0';
	}
	for(int i = 1 ; i <= m ; i ++)if(s[i] == '?'){
		if(!chk(i))	
			s[i] = '1';
	}
	for(int i = 1 ; i <= m ; i ++)
		cout << s[i];
	return(0);
}

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	17 ms	1004 KB	Output is correct
9	Correct	6 ms	876 KB	Output is correct
10	Correct	12 ms	876 KB	Output is correct
11	Correct	15 ms	1004 KB	Output is correct
12	Correct	11 ms	876 KB	Output is correct
13	Correct	10 ms	1004 KB	Output is correct
14	Correct	17 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	17 ms	1004 KB	Output is correct
9	Correct	6 ms	876 KB	Output is correct
10	Correct	12 ms	876 KB	Output is correct
11	Correct	15 ms	1004 KB	Output is correct
12	Correct	11 ms	876 KB	Output is correct
13	Correct	10 ms	1004 KB	Output is correct
14	Correct	17 ms	1004 KB	Output is correct
15	Correct	464 ms	7788 KB	Output is correct
16	Correct	3810 ms	9160 KB	Output is correct
17	Correct	1569 ms	10896 KB	Output is correct
18	Execution timed out	4053 ms	12652 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-