oj.uz

Submission #865928

# Submission time Handle Problem Language Result Execution time Memory
865928 2023-10-25T03:47:53 Z LittleOrange Lamps (JOI19_lamps) C++17
4 / 100
 27 ms 54220 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll l, r, t; // all0 all1 other
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    string a,b;
    cin >> n >> a >> b;
    vector<ll> c(n+1,0);
    for(ll i = 0;i<n;i++) c[i+1] = c[i] + b[i]-'0';
    vector<obj> v;
    ll last = -1,sm=0;
    for(ll i = 0;i<n;i++){
        if (a[i]!=b[i]){
            if (last==-1){
                last = i;
                sm = b[i]-'0';
            }else{
                sm+=b[i]-'0';
            }
        }else if (last!=-1){
            ll t = i-last==sm?1:(sm==0?0:2);
            v.push_back({last,i-1,t});
            last = -1;
        }
    }
    if (last!=-1){
        ll t = n-last==sm?1:(sm==0?0:2);
        v.push_back({last,n-1,t});
        last = -1;
    }
    ll ans = 0;
    vector<obj> nw;
    for(obj o : v){
        if (nw.empty()) nw.push_back(o);
        else{
            obj z = nw.back();
            if (o.t==z.t%3&&o.t!=2&&(c[o.l]-c[z.l]==(o.l-z.l)*o.t)){
                nw.pop_back();
                nw.push_back({z.l,o.r,o.t+3});
            }else nw.push_back(o);
        }
    }
    vector<obj> g;
    for(obj o : nw){
        if (g.size()<2) g.push_back(o);
        else{
            obj z = g[g.size()-2];
            if (z.t<3&&o.t<3&&(c[o.l]-c[z.r+1])%(o.l-(z.r+1))==0) g.pop_back();
            g.push_back(o);
        }
    }
    ans += g.size();
    for(obj o : g){
        //cout << "[" << o.l << "," << o.r << "] " << o.t << "\n"; 
    }
    cout << ans << "\n";
}

Compilation message

lamp.cpp: In function 'int main()':
lamp.cpp:57:13: warning: variable 'o' set but not used [-Wunused-but-set-variable]
   57 |     for(obj o : g){
      |             ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 10156 KB Output is correct
8 Correct 27 ms 53588 KB Output is correct
9 Correct 25 ms 52768 KB Output is correct
10 Correct 27 ms 53004 KB Output is correct
11 Correct 27 ms 54220 KB Output is correct
12 Correct 6 ms 10156 KB Output is correct
13 Correct 6 ms 10156 KB Output is correct
14 Correct 7 ms 11440 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -