# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
376551 |
2021-03-11T16:58:59 Z |
wiwiho |
Lamps (JOI19_lamps) |
C++14 |
|
1000 ms |
364 KB |
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 1LL << 60;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
struct status{
vector<vector<ll>> dp;
status(){
dp.resize(2, vector<ll>(2, MAX));
}
ll& get(int flip, int diff){
return dp[flip][diff];
}
void print(){
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++) cerr << dp[i][j] << ',';
}
cerr << "\n";
}
};
struct seg{
vector<vector<ll>> dp;
seg(){
dp.resize(2, vector<ll>(3, MAX));
}
ll& get(int flip, int all){
return dp[flip][all];
}
ll mn(){
ll ans = MAX;
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 2; j++) ans = min(ans, dp[i][j]);
}
}
void print(){
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 2; j++) cerr << dp[i][j] << ',';
}
cerr << "\n";
}
};
status transstatus(status from, int v){
status to;
for(int flip = 0; flip <= 1; flip++){
for(int diff = 0; diff <= 1; diff++){
if(!v && !diff) to.get(0, 0) = min(to.get(0, 0), from.get(flip, diff));
else to.get(0, 1) = min(to.get(0, 1), from.get(flip, diff));
if(v && !diff) to.get(1, 0) = min(to.get(1, 0), from.get(flip, diff) + !flip);
else to.get(1, 1) = min(to.get(1, 1), from.get(flip, diff) + !flip);
}
}
return to;
}
seg transseg(seg from, vector<int>& now){
seg to;
for(int flip = 0; flip <= 1; flip++){
for(int all = 0; all <= 2; all++){
status st;
st.get(flip, 0) = from.get(flip, all);
// cerr << "start " << flip << " " << all << "\n";
for(int i : now){
st = transstatus(st, i);
// cerr << "status " << i << " ";
// st.print();
}
for(int tf = 0; tf <= 1; tf++){
for(int diff = 0; diff <= 1; diff++){
if(!diff){
to.get(tf, 0) = min(to.get(tf, 0), st.get(tf, diff));
}
to.get(tf, 1) = min(to.get(tf, 1), st.get(tf, diff) + 1);
if(all == 1){
to.get(tf, 2) = min(to.get(tf, 2), st.get(tf, diff) + 1);
}
if(all == 2){
to.get(tf, 1) = min(to.get(tf, 1), st.get(tf, diff));
}
}
}
}
}
return to;
}
int main(){
StarBurstStream
int n;
cin >> n;
string a, b;
cin >> a >> b;
vector<vector<int>> now;
int lst = -1;
for(int i = 0; i < n; i++){
if(b[i] - '0' != lst) now.eb();
now.back().eb(b[i] != a[i]);
lst = b[i] - '0';
}
// for(auto& i : now) printv(i, cerr);
int m = now.size();
seg s;
s.get(0, 0) = 0;
for(int i = 0; i < m; i++){
s = transseg(s, now[i]);
// cerr << "seg " << i << " ";
// s.print();
}
cout << s.mn() << "\n";
return 0;
}
Compilation message
lamp.cpp: In member function 'll seg::mn()':
lamp.cpp:81:5: warning: no return statement in function returning non-void [-Wreturn-type]
81 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1051 ms |
364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1051 ms |
364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1084 ms |
364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1051 ms |
364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |