Submission #937679

#	Time	Username	Problem	Language	Result	Execution time	Memory
937679		wojciech_domin2	Lamps (JOI19_lamps)	C++14	4 / 100	73 ms	4084 KiB

lamp

#include <bits/stdc++.h>
#define pb push_back
#define ins insert
#define fi first
#define se second
#define debug(x) cout<<#x<<" = "<<x<<"\n";

using namespace std;
using ll = long long;
using ld = long double;

template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.fi<<", "<<m.se<<")";
}
 
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}

const int MAX_N = 1000020;
char A[MAX_N];
char B[MAX_N];
char D[MAX_N];

bitset<MAX_N> a,b,c;

int main(){
    int N;
    cin>>N;
    for(int i = 1; i <= N; i++){
        cin>>A[i];
    }
    for(int i = 1; i <= N; i++){
        cin>>B[i];
    }
 
    a[1] = int(A[1]^'0');
    b[1] = int(B[1]^'0');
    int lic = 2;
    for(int i = 2; i <= N; i++){
        if(A[i-1] == A[i] && B[i-1] == B[i]){
            //pomiń
        }else{
            a[lic] = int(A[i]^'0');
            b[lic] = int(B[i]^'0');
            lic++;
        }
    }
    c=a^b;
    //cout<<c<<"\n";
    for(int i = 0; i < MAX_N; i++){
         D[i]='*';
    }
    for(int i = 1; i < MAX_N-1; i++){
        if(c[i] && D[i] == '*') D[i] = 'x';
        if(c[i] && !c[i-1] && !c[i+1] && (D[i] == 'x' || D[i] == '*')){
            int j = i;
            while(j >= 1){
                if(b[j] == b[i]){
                    D[j] = char('0'^b[i]);
                }else{
                    break;
                }
                j--;
            }
            j=i;
            while(j <= N){
                if(b[j] == b[i]){
                    D[j] = char('0'^b[i]);
                }else{
                    break;
                }
                j++;
            }
        }
    }

    int odp = 0;
    int ixow = 0;
    int cnt = 0;
    char lit = '*';
    for(int i =1; i <= 7; i++){
      // cout<<D[i];
    }
    //cout<<endl;
    for(int i = 1; i < MAX_N; i++){
        if(D[i] != lit){
            if(D[i] == '*'){
                odp+=(cnt+2-ixow)/2;
                cnt = 0;
                ixow = 0;
            }
            if(D[i] == 'x'){
                ixow++;
                odp++;
                odp+=(cnt+2-ixow)/2;
                cnt = 0;
                ixow = 1;
            }
            if(D[i] == '0'){
                cnt++;
            }
            if(D[i] == '1'){
                cnt++;
            }
            lit = D[i];
        }
    }

    cout<<odp<<"\n";


    return 0;
}

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