Submission #865928

#	Time	Username	Problem	Language	Result	Execution time	Memory
865928		LittleOrange	Lamps (JOI19_lamps)	C++17	4 / 100	27 ms	54220 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll l, r, t; // all0 all1 other
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    string a,b;
    cin >> n >> a >> b;
    vector<ll> c(n+1,0);
    for(ll i = 0;i<n;i++) c[i+1] = c[i] + b[i]-'0';
    vector<obj> v;
    ll last = -1,sm=0;
    for(ll i = 0;i<n;i++){
        if (a[i]!=b[i]){
            if (last==-1){
                last = i;
                sm = b[i]-'0';
            }else{
                sm+=b[i]-'0';
            }
        }else if (last!=-1){
            ll t = i-last==sm?1:(sm==0?0:2);
            v.push_back({last,i-1,t});
            last = -1;
        }
    }
    if (last!=-1){
        ll t = n-last==sm?1:(sm==0?0:2);
        v.push_back({last,n-1,t});
        last = -1;
    }
    ll ans = 0;
    vector<obj> nw;
    for(obj o : v){
        if (nw.empty()) nw.push_back(o);
        else{
            obj z = nw.back();
            if (o.t==z.t%3&&o.t!=2&&(c[o.l]-c[z.l]==(o.l-z.l)*o.t)){
                nw.pop_back();
                nw.push_back({z.l,o.r,o.t+3});
            }else nw.push_back(o);
        }
    }
    vector<obj> g;
    for(obj o : nw){
        if (g.size()<2) g.push_back(o);
        else{
            obj z = g[g.size()-2];
            if (z.t<3&&o.t<3&&(c[o.l]-c[z.r+1])%(o.l-(z.r+1))==0) g.pop_back();
            g.push_back(o);
        }
    }
    ans += g.size();
    for(obj o : g){
        //cout << "[" << o.l << "," << o.r << "] " << o.t << "\n"; 
    }
    cout << ans << "\n";
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:57:13: warning: variable 'o' set but not used [-Wunused-but-set-variable]
   57 |     for(obj o : g){
      |             ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49