oj.uz

Submission #865028

# Submission time Handle Problem Language Result Execution time Memory
865028 2023-10-24T02:49:53 Z guagua0407 Lamps (JOI19_lamps) C++17
4 / 100
 179 ms 133028 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 Correct 10 ms 49752 KB Output is correct
2 Correct 10 ms 49756 KB Output is correct
3 Correct 11 ms 49804 KB Output is correct
4 Correct 10 ms 49756 KB Output is correct
5 Correct 10 ms 49816 KB Output is correct
6 Correct 11 ms 49756 KB Output is correct
7 Correct 10 ms 49756 KB Output is correct
8 Correct 10 ms 49752 KB Output is correct
9 Correct 11 ms 49756 KB Output is correct
10 Correct 10 ms 49632 KB Output is correct
11 Correct 10 ms 49756 KB Output is correct
12 Correct 10 ms 49756 KB Output is correct
13 Incorrect 11 ms 49756 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49752 KB Output is correct
2 Correct 10 ms 49756 KB Output is correct
3 Correct 11 ms 49804 KB Output is correct
4 Correct 10 ms 49756 KB Output is correct
5 Correct 10 ms 49816 KB Output is correct
6 Correct 11 ms 49756 KB Output is correct
7 Correct 10 ms 49756 KB Output is correct
8 Correct 10 ms 49752 KB Output is correct
9 Correct 11 ms 49756 KB Output is correct
10 Correct 10 ms 49632 KB Output is correct
11 Correct 10 ms 49756 KB Output is correct
12 Correct 10 ms 49756 KB Output is correct
13 Incorrect 11 ms 49756 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49752 KB Output is correct
2 Correct 10 ms 49756 KB Output is correct
3 Correct 10 ms 49756 KB Output is correct
4 Correct 10 ms 49752 KB Output is correct
5 Correct 10 ms 49804 KB Output is correct
6 Correct 10 ms 49756 KB Output is correct
7 Correct 24 ms 57260 KB Output is correct
8 Correct 177 ms 133028 KB Output is correct
9 Correct 177 ms 132480 KB Output is correct
10 Correct 179 ms 131840 KB Output is correct
11 Correct 176 ms 132996 KB Output is correct
12 Correct 28 ms 57264 KB Output is correct
13 Correct 27 ms 57332 KB Output is correct
14 Correct 37 ms 58864 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49752 KB Output is correct
2 Correct 10 ms 49756 KB Output is correct
3 Correct 11 ms 49804 KB Output is correct
4 Correct 10 ms 49756 KB Output is correct
5 Correct 10 ms 49816 KB Output is correct
6 Correct 11 ms 49756 KB Output is correct
7 Correct 10 ms 49756 KB Output is correct
8 Correct 10 ms 49752 KB Output is correct
9 Correct 11 ms 49756 KB Output is correct
10 Correct 10 ms 49632 KB Output is correct
11 Correct 10 ms 49756 KB Output is correct
12 Correct 10 ms 49756 KB Output is correct
13 Incorrect 11 ms 49756 KB Output isn't correct
14 Halted 0 ms 0 KB -