oj.uz

Submission #943863

# Submission time Handle Problem Language Result Execution time Memory
943863 2024-03-12T02:53:50 Z yeediot Lamps (JOI19_lamps) C++14
100 / 100
 61 ms 51456 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
const int mxn=1e6+5;
int dp[mxn][3][2];// [0/1/2]第i位用了on/off [0/1]第i位用了tog
void upd(int i,int l,int r,bool tf=1){
    for(int j=0;j<3;j++){
        for(int k=0;k<2;k++){
            int ad=0;
            if(l and l!=j)ad++;
            if(r and r!=k)ad++;
            chmin(dp[i][l][r],dp[i-1][j][k]+ad);
        }
    }
}
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    a=" "+a;
    b=" "+b;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++){
        if(a[i]==b[i]){
            upd(i,0,0,0);
        }
        if(a[i]=='0' and b[i]=='0'){
            upd(i,1,0);
            chmin(dp[i][1][0],min(dp[i-1][1][0],dp[i-1][1][1]));
            upd(i,2,1);
        }
        if(a[i]=='1' and b[i]=='1'){
            upd(i,2,0);
            chmin(dp[i][2][0],min(dp[i-1][2][0],dp[i-1][2][1]));
            upd(i,1,1);
        }
        if(a[i]=='1' and b[i]=='0'){
            upd(i,1,0);
            chmin(dp[i][1][0],min(dp[i-1][1][0],dp[i-1][1][1]));
            upd(i,0,1);
            chmin(dp[i][0][1],min({dp[i-1][0][1],dp[i-1][1][1],dp[i-1][2][1]}));
            upd(i,2,1);
        }
        if(a[i]=='0' and b[i]=='1'){
            upd(i,2,0);
            chmin(dp[i][2][0],min(dp[i-1][2][0],dp[i-1][2][1]));
            upd(i,0,1);
            chmin(dp[i][0][1],min({dp[i-1][0][1],dp[i-1][1][1],dp[i-1][2][1]}));
            upd(i,1,1);
        }
        debug(dp[i][0][0],dp[i][0][1],dp[i][1][0],dp[i][1][1],dp[i][2][0],dp[i][2][1]);
    }
    cout<<min({dp[n][0][0],dp[n][0][1],dp[n][1][0],dp[n][1][1],dp[n][2][0],dp[n][2][1]})<<'\n';
}
 /*
 input:
 
 */

Compilation message

lamp.cpp: In function 'void setIO(std::string)':
lamp.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47196 KB Output is correct
2 Correct 7 ms 47196 KB Output is correct
3 Correct 7 ms 47196 KB Output is correct
4 Correct 6 ms 47196 KB Output is correct
5 Correct 16 ms 47192 KB Output is correct
6 Correct 8 ms 47192 KB Output is correct
7 Correct 8 ms 47196 KB Output is correct
8 Correct 7 ms 47192 KB Output is correct
9 Correct 7 ms 47196 KB Output is correct
10 Correct 6 ms 47252 KB Output is correct
11 Correct 6 ms 47312 KB Output is correct
12 Correct 7 ms 47196 KB Output is correct
13 Correct 6 ms 47192 KB Output is correct
14 Correct 7 ms 47240 KB Output is correct
15 Correct 8 ms 47196 KB Output is correct
16 Correct 7 ms 47312 KB Output is correct
17 Correct 7 ms 47312 KB Output is correct
18 Correct 6 ms 47196 KB Output is correct
19 Correct 7 ms 47196 KB Output is correct
20 Correct 7 ms 47312 KB Output is correct
21 Correct 7 ms 47196 KB Output is correct
22 Correct 7 ms 47196 KB Output is correct
23 Correct 7 ms 47196 KB Output is correct
24 Correct 7 ms 47192 KB Output is correct
25 Correct 7 ms 47196 KB Output is correct
26 Correct 7 ms 47252 KB Output is correct
27 Correct 8 ms 47196 KB Output is correct
28 Correct 10 ms 47192 KB Output is correct
29 Correct 11 ms 47544 KB Output is correct
30 Correct 8 ms 47192 KB Output is correct
31 Correct 7 ms 47196 KB Output is correct
32 Correct 7 ms 47196 KB Output is correct
33 Correct 15 ms 47196 KB Output is correct
34 Correct 7 ms 47240 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47196 KB Output is correct
2 Correct 7 ms 47196 KB Output is correct
3 Correct 7 ms 47196 KB Output is correct
4 Correct 6 ms 47196 KB Output is correct
5 Correct 16 ms 47192 KB Output is correct
6 Correct 8 ms 47192 KB Output is correct
7 Correct 8 ms 47196 KB Output is correct
8 Correct 7 ms 47192 KB Output is correct
9 Correct 7 ms 47196 KB Output is correct
10 Correct 6 ms 47252 KB Output is correct
11 Correct 6 ms 47312 KB Output is correct
12 Correct 7 ms 47196 KB Output is correct
13 Correct 6 ms 47192 KB Output is correct
14 Correct 7 ms 47240 KB Output is correct
15 Correct 8 ms 47196 KB Output is correct
16 Correct 7 ms 47312 KB Output is correct
17 Correct 7 ms 47312 KB Output is correct
18 Correct 6 ms 47196 KB Output is correct
19 Correct 7 ms 47196 KB Output is correct
20 Correct 7 ms 47312 KB Output is correct
21 Correct 7 ms 47196 KB Output is correct
22 Correct 7 ms 47196 KB Output is correct
23 Correct 7 ms 47196 KB Output is correct
24 Correct 7 ms 47192 KB Output is correct
25 Correct 7 ms 47196 KB Output is correct
26 Correct 7 ms 47252 KB Output is correct
27 Correct 8 ms 47196 KB Output is correct
28 Correct 10 ms 47192 KB Output is correct
29 Correct 11 ms 47544 KB Output is correct
30 Correct 8 ms 47192 KB Output is correct
31 Correct 7 ms 47196 KB Output is correct
32 Correct 7 ms 47196 KB Output is correct
33 Correct 15 ms 47196 KB Output is correct
34 Correct 7 ms 47240 KB Output is correct
35 Correct 6 ms 47192 KB Output is correct
36 Correct 7 ms 47196 KB Output is correct
37 Correct 6 ms 47316 KB Output is correct
38 Correct 6 ms 47196 KB Output is correct
39 Correct 6 ms 47196 KB Output is correct
40 Correct 6 ms 47316 KB Output is correct
41 Correct 12 ms 47300 KB Output is correct
42 Correct 8 ms 47196 KB Output is correct
43 Correct 7 ms 47308 KB Output is correct
44 Correct 7 ms 47308 KB Output is correct
45 Correct 8 ms 47196 KB Output is correct
46 Correct 8 ms 47196 KB Output is correct
47 Correct 7 ms 47276 KB Output is correct
48 Correct 8 ms 47196 KB Output is correct
49 Correct 7 ms 47328 KB Output is correct
50 Correct 9 ms 47308 KB Output is correct
51 Correct 6 ms 47308 KB Output is correct
52 Correct 6 ms 47192 KB Output is correct
53 Correct 6 ms 47196 KB Output is correct
54 Correct 7 ms 47196 KB Output is correct
55 Correct 7 ms 47196 KB Output is correct
56 Correct 8 ms 47316 KB Output is correct
57 Correct 8 ms 47308 KB Output is correct
58 Correct 7 ms 47196 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47196 KB Output is correct
2 Correct 8 ms 47312 KB Output is correct
3 Correct 7 ms 47196 KB Output is correct
4 Correct 7 ms 47284 KB Output is correct
5 Correct 7 ms 47192 KB Output is correct
6 Correct 12 ms 47196 KB Output is correct
7 Correct 34 ms 51196 KB Output is correct
8 Correct 38 ms 51200 KB Output is correct
9 Correct 38 ms 51160 KB Output is correct
10 Correct 42 ms 51456 KB Output is correct
11 Correct 36 ms 51264 KB Output is correct
12 Correct 40 ms 51096 KB Output is correct
13 Correct 35 ms 51200 KB Output is correct
14 Correct 35 ms 51208 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47196 KB Output is correct
2 Correct 7 ms 47196 KB Output is correct
3 Correct 7 ms 47196 KB Output is correct
4 Correct 6 ms 47196 KB Output is correct
5 Correct 16 ms 47192 KB Output is correct
6 Correct 8 ms 47192 KB Output is correct
7 Correct 8 ms 47196 KB Output is correct
8 Correct 7 ms 47192 KB Output is correct
9 Correct 7 ms 47196 KB Output is correct
10 Correct 6 ms 47252 KB Output is correct
11 Correct 6 ms 47312 KB Output is correct
12 Correct 7 ms 47196 KB Output is correct
13 Correct 6 ms 47192 KB Output is correct
14 Correct 7 ms 47240 KB Output is correct
15 Correct 8 ms 47196 KB Output is correct
16 Correct 7 ms 47312 KB Output is correct
17 Correct 7 ms 47312 KB Output is correct
18 Correct 6 ms 47196 KB Output is correct
19 Correct 7 ms 47196 KB Output is correct
20 Correct 7 ms 47312 KB Output is correct
21 Correct 7 ms 47196 KB Output is correct
22 Correct 7 ms 47196 KB Output is correct
23 Correct 7 ms 47196 KB Output is correct
24 Correct 7 ms 47192 KB Output is correct
25 Correct 7 ms 47196 KB Output is correct
26 Correct 7 ms 47252 KB Output is correct
27 Correct 8 ms 47196 KB Output is correct
28 Correct 10 ms 47192 KB Output is correct
29 Correct 11 ms 47544 KB Output is correct
30 Correct 8 ms 47192 KB Output is correct
31 Correct 7 ms 47196 KB Output is correct
32 Correct 7 ms 47196 KB Output is correct
33 Correct 15 ms 47196 KB Output is correct
34 Correct 7 ms 47240 KB Output is correct
35 Correct 6 ms 47192 KB Output is correct
36 Correct 7 ms 47196 KB Output is correct
37 Correct 6 ms 47316 KB Output is correct
38 Correct 6 ms 47196 KB Output is correct
39 Correct 6 ms 47196 KB Output is correct
40 Correct 6 ms 47316 KB Output is correct
41 Correct 12 ms 47300 KB Output is correct
42 Correct 8 ms 47196 KB Output is correct
43 Correct 7 ms 47308 KB Output is correct
44 Correct 7 ms 47308 KB Output is correct
45 Correct 8 ms 47196 KB Output is correct
46 Correct 8 ms 47196 KB Output is correct
47 Correct 7 ms 47276 KB Output is correct
48 Correct 8 ms 47196 KB Output is correct
49 Correct 7 ms 47328 KB Output is correct
50 Correct 9 ms 47308 KB Output is correct
51 Correct 6 ms 47308 KB Output is correct
52 Correct 6 ms 47192 KB Output is correct
53 Correct 6 ms 47196 KB Output is correct
54 Correct 7 ms 47196 KB Output is correct
55 Correct 7 ms 47196 KB Output is correct
56 Correct 8 ms 47316 KB Output is correct
57 Correct 8 ms 47308 KB Output is correct
58 Correct 7 ms 47196 KB Output is correct
59 Correct 7 ms 47196 KB Output is correct
60 Correct 8 ms 47312 KB Output is correct
61 Correct 7 ms 47196 KB Output is correct
62 Correct 7 ms 47284 KB Output is correct
63 Correct 7 ms 47192 KB Output is correct
64 Correct 12 ms 47196 KB Output is correct
65 Correct 34 ms 51196 KB Output is correct
66 Correct 38 ms 51200 KB Output is correct
67 Correct 38 ms 51160 KB Output is correct
68 Correct 42 ms 51456 KB Output is correct
69 Correct 36 ms 51264 KB Output is correct
70 Correct 40 ms 51096 KB Output is correct
71 Correct 35 ms 51200 KB Output is correct
72 Correct 35 ms 51208 KB Output is correct
73 Correct 37 ms 51152 KB Output is correct
74 Correct 45 ms 51096 KB Output is correct
75 Correct 38 ms 51148 KB Output is correct
76 Correct 45 ms 51200 KB Output is correct
77 Correct 35 ms 51128 KB Output is correct
78 Correct 39 ms 51124 KB Output is correct
79 Correct 35 ms 51196 KB Output is correct
80 Correct 40 ms 51244 KB Output is correct
81 Correct 34 ms 51208 KB Output is correct
82 Correct 46 ms 51208 KB Output is correct
83 Correct 38 ms 51128 KB Output is correct
84 Correct 52 ms 51204 KB Output is correct
85 Correct 38 ms 51280 KB Output is correct
86 Correct 38 ms 51200 KB Output is correct
87 Correct 38 ms 51152 KB Output is correct
88 Correct 42 ms 51232 KB Output is correct
89 Correct 50 ms 51232 KB Output is correct
90 Correct 38 ms 51156 KB Output is correct
91 Correct 51 ms 51192 KB Output is correct
92 Correct 43 ms 51280 KB Output is correct
93 Correct 42 ms 51204 KB Output is correct
94 Correct 56 ms 51100 KB Output is correct
95 Correct 48 ms 51204 KB Output is correct
96 Correct 61 ms 51196 KB Output is correct
97 Correct 43 ms 51144 KB Output is correct
98 Correct 45 ms 51204 KB Output is correct
99 Correct 48 ms 51444 KB Output is correct
100 Correct 43 ms 51224 KB Output is correct
101 Correct 47 ms 51224 KB Output is correct
102 Correct 44 ms 51328 KB Output is correct