oj.uz

Submission #370220

# Submission time Handle Problem Language Result Execution time Memory
370220 2021-02-23T15:12:33 Z soroush Ili (COI17_ili) C++17
49 / 100
 4000 ms 12964 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){
	if(x[pos].count() > 8000){
		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);
		}
	}
	else{
		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 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 2 ms 1004 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 1004 KB Output is correct
12 Correct 2 ms 876 KB Output is correct
13 Correct 2 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 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 2 ms 1004 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 1004 KB Output is correct
12 Correct 2 ms 876 KB Output is correct
13 Correct 2 ms 1004 KB Output is correct
14 Correct 2 ms 1004 KB Output is correct
15 Correct 22 ms 7916 KB Output is correct
16 Correct 49 ms 9196 KB Output is correct
17 Correct 36 ms 11000 KB Output is correct
18 Correct 129 ms 12780 KB Output is correct
19 Correct 90 ms 9324 KB Output is correct
20 Correct 340 ms 12796 KB Output is correct
21 Correct 770 ms 12964 KB Output is correct
22 Correct 617 ms 12396 KB Output is correct
23 Correct 627 ms 12932 KB Output is correct
24 Correct 583 ms 12936 KB Output is correct
25 Execution timed out 4070 ms 12780 KB Time limit exceeded
26 Halted 0 ms 0 KB -