oj.uz

Submission #370206

# Submission time Handle Problem Language Result Execution time Memory
370206 2021-02-23T15:03:14 Z soroush Ili (COI17_ili) C++14
49 / 100
 4000 ms 12780 KB 
#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){
	for(int i : ans[1]){
		bool ok = 0;
		for(int j = x[i]._Find_first() ; j < maxn ; j = x[i]._Find_next(j))
			if(x[pos][j] == 0){
				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 0 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 0 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 0 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 0 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 2 ms 1036 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 1004 KB Output is correct
12 Correct 2 ms 876 KB Output is correct
13 Correct 1 ms 1004 KB Output is correct
14 Correct 2 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 0 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 0 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 2 ms 1036 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 1004 KB Output is correct
12 Correct 2 ms 876 KB Output is correct
13 Correct 1 ms 1004 KB Output is correct
14 Correct 2 ms 1004 KB Output is correct
15 Correct 18 ms 7788 KB Output is correct
16 Correct 45 ms 9068 KB Output is correct
17 Correct 33 ms 10860 KB Output is correct
18 Correct 137 ms 12652 KB Output is correct
19 Correct 94 ms 9324 KB Output is correct
20 Correct 352 ms 12652 KB Output is correct
21 Correct 881 ms 12780 KB Output is correct
22 Correct 698 ms 12268 KB Output is correct
23 Correct 723 ms 12768 KB Output is correct
24 Correct 690 ms 12744 KB Output is correct
25 Execution timed out 4029 ms 12780 KB Time limit exceeded
26 Halted 0 ms 0 KB -