Submission #379351

#	Time	Username	Problem	Language	Result	Execution time	Memory
379351		balbit	Lamps (JOI19_lamps)	C++14	100 / 100	84 ms	27884 KiB

lamp

#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 = 1e6+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 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49