oj.uz

Submission #144945

# Submission time Handle Problem Language Result Execution time Memory
144945 2019-08-18T08:51:16 Z LeMur Ili (COI17_ili) C++14
100 / 100
 581 ms 13404 KB 
////////////////////////////////////////////    _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 10005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;

int n , m;
string s;

bitset <N> mas[N];
bitset <N> A;
vector <int> vec;

vector <int> g;
vector < pair<char,int> > gg[N];

int C[N] , X[N];

bool check(int id){
    for(int i=0;i<n;i++){
        if(mas[id][i])
            X[i] = 0;
        else
            X[i] = A[i] ^ 1;
    }
    for(int i=0;i<m;i++){
        int a = (gg[i][0].first == 'c') ? C[ gg[i][0].second ] : X[ gg[i][0].second ];
        int b = (gg[i][1].first == 'c') ? C[ gg[i][1].second ] : X[ gg[i][1].second ];
        C[i] = (a | b);
        if(s[i] == '1' && C[i] == 0)return true;
    }
    return false;
}

int main(){
	mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> m;
    cin >> s;
    for(int i=0;i<m;i++){
        char c1 , c2;
        int x1 , x2;
        cin >> c1 >> x1;
        cin >> c2 >> x2;
        --x1;
        --x2;
        if(c1 == 'x')
            mas[i][x1] = '1';
        else
            mas[i] |= mas[x1];
        if(c2 == 'x')
            mas[i][x2] = '1';
        else
            mas[i] |= mas[x2];

        gg[i].push_back(make_pair(c1 , x1));
        gg[i].push_back(make_pair(c2 , x2));

        if(s[i] == '0'){
            A |= mas[i];
        }
        if(s[i] == '1'){
            vec.push_back(i);
        }
    }
    for(int i=0;i<n;i++){
        if(A[i] == 1){
            for(int j=0;j<m;j++){
                mas[j][i] = 0;
            }
        }
    }
    for(int j=0;j<m;j++){
        if(mas[j].count() == 0){
            s[j] = '0';
        }
    }
    for(int i=0;i<m;i++){
        if(s[i] == '?'){
            if(check(i)){
                s[i] = '1';
            }
        }
    }
    cout << s << endl;
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 4 ms 1144 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 4 ms 1272 KB Output is correct
11 Correct 4 ms 1148 KB Output is correct
12 Correct 4 ms 1144 KB Output is correct
13 Correct 4 ms 1144 KB Output is correct
14 Correct 4 ms 1144 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 4 ms 1144 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 4 ms 1272 KB Output is correct
11 Correct 4 ms 1148 KB Output is correct
12 Correct 4 ms 1144 KB Output is correct
13 Correct 4 ms 1144 KB Output is correct
14 Correct 4 ms 1144 KB Output is correct
15 Correct 39 ms 8312 KB Output is correct
16 Correct 153 ms 9528 KB Output is correct
17 Correct 81 ms 11256 KB Output is correct
18 Correct 335 ms 13048 KB Output is correct
19 Correct 147 ms 9592 KB Output is correct
20 Correct 512 ms 13116 KB Output is correct
21 Correct 581 ms 13304 KB Output is correct
22 Correct 137 ms 12792 KB Output is correct
23 Correct 146 ms 13188 KB Output is correct
24 Correct 140 ms 13176 KB Output is correct
25 Correct 236 ms 13140 KB Output is correct
26 Correct 233 ms 12996 KB Output is correct
27 Correct 240 ms 13032 KB Output is correct
28 Correct 214 ms 12792 KB Output is correct
29 Correct 220 ms 12792 KB Output is correct
30 Correct 235 ms 12944 KB Output is correct
31 Correct 218 ms 13404 KB Output is correct
32 Correct 237 ms 13400 KB Output is correct