oj.uz

Submission #379350

# Submission time Handle Problem Language Result Execution time Memory
379350 2021-03-18T02:37:54 Z balbit Lamps (JOI19_lamps) C++14
47 / 100
 3 ms 2688 KB 
#include <bits/stdc++.h>
//#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif


void GG(){cout<<"0\n"; exit(0);}
const ll mod = 1e9+7;
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;

bool a[maxn], b[maxn];
int dp[maxn][2][3];
int n;
ll bad(){
    memset (dp, 0x3f, sizeof dp);
    int re = inf;
    dp[0][0][0] = 0;
    dp[0][1][0] = 1;
    REP1(i,n) {
        REP(flip, 2) {
            REP(fl, 3) {
                int &me = dp[i][flip][fl];
                if (fl == 0) {
                    if (flip == (a[i] ^ b[i])) {
                        MN(me, dp[i-1][flip][1]);
                        MN(me, dp[i-1][flip][2]);
                        MN(me, dp[i-1][flip][0]);
                        MN(me, dp[i-1][flip^1][0]+(flip==1));
                        MN(me, dp[i-1][flip^1][1] + (flip==1));
                        MN(me, dp[i-1][flip^1][2]);
                    }
                }else{
                    if (fl == 1)
                        MN(me, dp[i-1][flip][0]+1);

                    if (b[i] != b[i-1]) {
                        MN(me, dp[i-1][flip][fl^3] + (fl == 2));
                        if (fl == 1 && flip == 0) {
                            MN(me, dp[i-1][flip^1][1]);
                        }
                    }else{
                        MN(me, dp[i-1][flip][fl]);
                    }
                }
                if (i == n) {
                    MN(re, dp[i][flip][fl]);
                }
            }
        }
    }
    return re;
}

int fast[(1<<11)];

ll dumb(int A, int B, int n){
    memset(fast, 0x3f, sizeof fast);
    fast[B] = 0;
    queue<int> q; q.push(B);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        REP(r,n) REP(l,r+1) {
            bool zero=0, one=0;
            for (int c = l; c<=r; ++c) {
                if (v & (1<<c)) one = 1;
                else zero = 1;
            }
            if ((!zero) || (!one)) {
                for (int m = 0; m<(1<<(r-l+1)); ++m) {
                    int tv = v;
                    for (int c = l; c<=r; ++c) {
                        if (m & (1<<(c-l))) {
                            tv ^= (1<<c);
                        }
                    }
                    if (fast[tv] > fast[v] + 1) {
                        if (tv == A) {
                            bug(l,r,m,v);
                            REP(i,n) cout<<((v&(1<<i))?'1':'0');
                            cout<<endl;
                        }
                        fast[tv]  =fast[v] + 1;
                        q.push(tv);
                    }
                }
            }
            {
                int tv = v;
                for (int c = l; c<=r; ++c) {
                    tv ^= (1<<c);
                }
                if (fast[tv] > fast[v] + 1) {
                    if (tv == A) {
                        bug(l,r,"flip",v,B);
                        REP(i,n) cout<<((v&(1<<i))?'1':'0');
                            cout<<endl;
                    }
                    fast[tv] = fast[v] + 1;
                    q.push(tv);
                }
            }
        }
    }
    return fast[A];
}

signed main(){
    IOS();
    cin>>n;
    #ifndef BALBIT
    REP1(i,n) {
        char c; cin>>c; a[i] = c=='1';
    }
    REP1(i,n) {
        char c; cin>>c; b[i] = c=='1';
    }
    cout<<bad()<<endl;
    #else
    REP(i, 1000) {
        int A = 0, B = 0;
        REP1(i,n) {
            a[i] = rand() % 2;
            if (a[i]) A += (1<<(i-1));
            b[i] = rand() % 2;
            if (b[i]) B += (1<<(i-1));
        }
        ll hi = dumb(A,B,n);
        ll death = bad();
        if (hi != death) {
            REP1(i,n) cout<<a[i];
            cout<<endl;
            REP1(i,n) cout<<b[i];
            cout<<endl;
            cout<<hi<<' '<<death<<endl;
            assert(0);
        }
    }
    #endif

}
/*
7
0101001
1110010
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 2 ms 2668 KB Output is correct
22 Correct 2 ms 2668 KB Output is correct
23 Correct 2 ms 2668 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2668 KB Output is correct
26 Correct 2 ms 2668 KB Output is correct
27 Correct 2 ms 2668 KB Output is correct
28 Correct 2 ms 2668 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2668 KB Output is correct
31 Correct 2 ms 2668 KB Output is correct
32 Correct 2 ms 2668 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 2 ms 2668 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 2 ms 2668 KB Output is correct
22 Correct 2 ms 2668 KB Output is correct
23 Correct 2 ms 2668 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2668 KB Output is correct
26 Correct 2 ms 2668 KB Output is correct
27 Correct 2 ms 2668 KB Output is correct
28 Correct 2 ms 2668 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2668 KB Output is correct
31 Correct 2 ms 2668 KB Output is correct
32 Correct 2 ms 2668 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 2 ms 2668 KB Output is correct
35 Correct 2 ms 2668 KB Output is correct
36 Correct 2 ms 2668 KB Output is correct
37 Correct 2 ms 2668 KB Output is correct
38 Correct 2 ms 2668 KB Output is correct
39 Correct 2 ms 2668 KB Output is correct
40 Correct 2 ms 2668 KB Output is correct
41 Correct 2 ms 2668 KB Output is correct
42 Correct 2 ms 2668 KB Output is correct
43 Correct 2 ms 2668 KB Output is correct
44 Correct 2 ms 2668 KB Output is correct
45 Correct 2 ms 2668 KB Output is correct
46 Correct 2 ms 2668 KB Output is correct
47 Correct 2 ms 2668 KB Output is correct
48 Correct 2 ms 2668 KB Output is correct
49 Correct 2 ms 2668 KB Output is correct
50 Correct 2 ms 2668 KB Output is correct
51 Correct 2 ms 2668 KB Output is correct
52 Correct 2 ms 2668 KB Output is correct
53 Correct 2 ms 2668 KB Output is correct
54 Correct 2 ms 2668 KB Output is correct
55 Correct 3 ms 2688 KB Output is correct
56 Correct 2 ms 2668 KB Output is correct
57 Correct 2 ms 2668 KB Output is correct
58 Correct 2 ms 2668 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Runtime error 3 ms 1004 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 2 ms 2668 KB Output is correct
22 Correct 2 ms 2668 KB Output is correct
23 Correct 2 ms 2668 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2668 KB Output is correct
26 Correct 2 ms 2668 KB Output is correct
27 Correct 2 ms 2668 KB Output is correct
28 Correct 2 ms 2668 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2668 KB Output is correct
31 Correct 2 ms 2668 KB Output is correct
32 Correct 2 ms 2668 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 2 ms 2668 KB Output is correct
35 Correct 2 ms 2668 KB Output is correct
36 Correct 2 ms 2668 KB Output is correct
37 Correct 2 ms 2668 KB Output is correct
38 Correct 2 ms 2668 KB Output is correct
39 Correct 2 ms 2668 KB Output is correct
40 Correct 2 ms 2668 KB Output is correct
41 Correct 2 ms 2668 KB Output is correct
42 Correct 2 ms 2668 KB Output is correct
43 Correct 2 ms 2668 KB Output is correct
44 Correct 2 ms 2668 KB Output is correct
45 Correct 2 ms 2668 KB Output is correct
46 Correct 2 ms 2668 KB Output is correct
47 Correct 2 ms 2668 KB Output is correct
48 Correct 2 ms 2668 KB Output is correct
49 Correct 2 ms 2668 KB Output is correct
50 Correct 2 ms 2668 KB Output is correct
51 Correct 2 ms 2668 KB Output is correct
52 Correct 2 ms 2668 KB Output is correct
53 Correct 2 ms 2668 KB Output is correct
54 Correct 2 ms 2668 KB Output is correct
55 Correct 3 ms 2688 KB Output is correct
56 Correct 2 ms 2668 KB Output is correct
57 Correct 2 ms 2668 KB Output is correct
58 Correct 2 ms 2668 KB Output is correct
59 Correct 2 ms 2668 KB Output is correct
60 Correct 2 ms 2668 KB Output is correct
61 Correct 2 ms 2688 KB Output is correct
62 Correct 2 ms 2668 KB Output is correct
63 Correct 2 ms 2668 KB Output is correct
64 Correct 2 ms 2668 KB Output is correct
65 Runtime error 3 ms 1004 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -