oj.uz

Submission #250804

# Submission time Handle Problem Language Result Execution time Memory
250804 2020-07-19T07:59:31 Z ne4eHbKa Ili (COI17_ili) C++17
100 / 100
 2051 ms 12968 KB 
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

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

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e4 + 5;
typedef bitset<N> bt;

int n, m;
string f;

bt nl;

struct u;

u* get(int);

struct u {
    bt f;
    void read(char c) {
        char a, b; int A, B;
        cin >> a >> A >> b >> B;
        --A, --B;
        f.reset();
        if(a == 'c') f |= get(A)->f; else f.set(A);
        if(b == 'c') f |= get(B)->f; else f.set(B);
        if(c == '0') nl |= f;
    }
};

u z[N];

u* get(int i) {re &z[i];}

void solve() {
    cin >> n >> m >> f;
    nl.reset();
    fo(m) z[i].read(f[i]);
    nl.flip();
    fo(m) z[i].f &= nl;
    fo(m) if(z[i].f.none()) f[i] = '0';
    vector<int> p(m);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&] (const int &a, const int &b) {
        int le = z[a].f.count();
        int ri = z[b].f.count();
        if(le != ri) re le < ri;
        if(f[a] == '1' && f[b] != '1') re true;
        if(f[a] != '1' && f[b] == '1') re false;
        re a < b;
    });
    list<int> u;
    for(int i : p) {
        bt R = ~z[i].f;
        for(int j : u) if((z[j].f & R).none()) {
            f[i] = '1';
            goto nx;
        }
        if(f[i] == '1') u.pb(i);
        nx:;
    }
    cout << f << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

ili.cpp: In function 'int m_bpow(ll, ll)':
ili.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 7 ms 896 KB Output is correct
12 Correct 6 ms 896 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 6 ms 1024 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 7 ms 896 KB Output is correct
12 Correct 6 ms 896 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 6 ms 1024 KB Output is correct
15 Correct 95 ms 7888 KB Output is correct
16 Correct 204 ms 9088 KB Output is correct
17 Correct 186 ms 10880 KB Output is correct
18 Correct 734 ms 12752 KB Output is correct
19 Correct 204 ms 9216 KB Output is correct
20 Correct 1092 ms 12968 KB Output is correct
21 Correct 1630 ms 12884 KB Output is correct
22 Correct 1971 ms 12408 KB Output is correct
23 Correct 2051 ms 12792 KB Output is correct
24 Correct 1941 ms 12908 KB Output is correct
25 Correct 182 ms 12672 KB Output is correct
26 Correct 181 ms 12704 KB Output is correct
27 Correct 185 ms 12624 KB Output is correct
28 Correct 179 ms 12288 KB Output is correct
29 Correct 174 ms 12536 KB Output is correct
30 Correct 183 ms 12536 KB Output is correct
31 Correct 151 ms 12800 KB Output is correct
32 Correct 144 ms 12800 KB Output is correct