oj.uz

Submission #865027

# Submission time Handle Problem Language Result Execution time Memory
865027 2023-10-24T02:49:09 Z guagua0407 Lamps (JOI19_lamps) C++17
0 / 100
 10 ms 49756 KB 
//#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 49752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 49752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 49756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 49752 KB Output isn't correct
2 Halted 0 ms 0 KB -