Submission #865028

#	Time	Username	Problem	Language	Result	Execution time	Memory
865028		guagua0407	Lamps (JOI19_lamps)	C++17	4 / 100	179 ms	133028 KiB

lamp

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s+ ".out").c_str(), "w", stdout);
}

const int mxn=1e6+5;
int a[mxn];
int dp[mxn];
vector<int> st[mxn],en[mxn];

int main() {_
    int n;
    cin>>n;
    string A,B;
    cin>>A>>B;
    map<pair<char,char>,int> mp;
    mp[{'0','0'}]=1;
    mp[{'1','1'}]=2;
    mp[{'1','0'}]=3;
    mp[{'0','1'}]=4;
    for(int i=0;i<n;i++){
        a[i+1]=mp[{A[i],B[i]}];
    }
    vector<pair<int,int>> vec;
    {
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]!=1 and a[i]!=3){
                if(cnt>0){
                    vec.push_back({i-1-cnt+1,i-1});
                }
                cnt=0;
            }
            else{
                cnt++;
            }
        }
        if(cnt>0){
            vec.push_back({n-cnt+1,n});
        }
    }
    {
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]!=2 and a[i]!=4){
                if(cnt>0){
                    vec.push_back({i-1-cnt+1,i-1});
                }
                cnt=0;
            }
            else{
                cnt++;
            }
        }
        if(cnt>0){
            vec.push_back({n-cnt+1,n});
        }
    }
    {
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]!=3 and a[i]!=4){
                if(cnt>0){
                    vec.push_back({i-1-cnt+1,i-1});
                }
                cnt=0;
            }
            else{
                cnt++;
            }
        }
        if(cnt>0){
            vec.push_back({n-cnt+1,n});
        }
    }
    for(int i=0;i<vec.size();i++){
        st[vec[i].f].push_back(i);
        en[vec[i].s+1].push_back(i);
    }
    multiset<int> S;
    for(int i=1;i<=n;i++){
        for(auto v:st[i]){
            S.insert(i);
        }
        for(auto v:en[i]){
            S.erase(S.find(vec[v].f));
        }
        assert(!S.empty());
        dp[i]=dp[i-1]+(a[i]==3 or a[i]==4);
        for(auto v:S){
            dp[i]=min(dp[i],dp[v-1]+1);
        }
    }
    /*for(auto v:vec){
        cout<<v.f<<' '<<v.s<<'\n';
    }
    for(int i=1;i<=n;i++){
        cout<<dp[i]<<' ';
    }
    cout<<'\n';*/
    cout<<dp[n]<<'\n';
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
lamp.cpp:92:18: warning: unused variable 'v' [-Wunused-variable]
   92 |         for(auto v:st[i]){
      |                  ^
lamp.cpp: In function 'void setIO(std::string)':
lamp.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s+ ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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