oj.uz

Submission #630560

# Submission time Handle Problem Language Result Execution time Memory
630560 2022-08-16T14:12:54 Z cadmiumsky Lamps (JOI19_lamps) C++14
0 / 100
 81 ms 44468 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

// imi bag ceva ca daca nu da AC nu ma mai ating de jegul asta vreodata

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
struct box {int c[2] = {0, 0}, type = 1; box(int a, int b, int z) {tie(c[0], c[1]) = pii{a, b}, type = z; }
  int get() { if(c[0] < c[1]) return 2; if(c[1] < c[0]) return 1; return 3; }
  bool comp(int x) { 
    int accum = 0;
    if(x == 0) return 0;
    if(x & 1) accum |= (c[1] == 0);
    if(x & 2) accum |= (c[0] == 0);
    return accum;
  }
};

const int inf = 1e9 + 5, nmax = 2e5 + 5;
int dp[nmax][2][2];

signed main() {
  int n;
  cin >> n;
  string A, B;
  cin >> A >> B;
  A = "#" + A + "@";
  B = "#" + B + "@";
  
  vector<box> elems;
  elems.emplace_back(1, 1, 0);
  for(int i = 1; i <= n; i++) {
    bool trigger = 0;
    if((A[i] ^ B[i]) != (A[i - 1] ^ B[i - 1]))
      //cerr << i << ' ' << (A[i] ^ B[i]) << ' ' << (A[i - 1] ^ B[i - 1]) << '\n',
      elems.emplace_back(0, 0, A[i] != B[i]),
      trigger = 1;
    if(B[i] != B[i - 1] || trigger)
      elems.back().c['1' - B[i]]++;
  }
  
  vector<int> nasp(elems.size());
  for(int i = 0; i < elems.size(); i++)
    for(int u = 0; u < 4; u++)
      dp[i][u & 1][u >> 1] = inf;
  for(int i = 1; i < elems.size(); i++) {  
    if(elems[i].type == 0) {      
      nasp[i] = nasp[i - 1];
      for(int u = 0; u < 4; u++)
	nasp[i] = min(nasp[i], dp[i - 1][u & 1][u >> 1]);
      
      if(elems[i].c[0] > 0 && elems[i].c[1] > 0)
	true;
      else {
	int val = 1;
	if(elems[i].c[1] == 1)
	  val = 0;
      
	dp[i][!val][0] = inf;
	dp[i][!val][1] = min({elems[i - 1].type == 1? nasp[i - 1] + 1 : inf, dp[i - 1][!val][0] + 1, dp[i - 1][!val][1]});
	dp[i][val][1] = inf;
	dp[i][val][0] = min({elems[i - 1].type == 1? nasp[i - 1] + 2 : inf, dp[i - 1][val][0], dp[i - 1][val][1]});
      }
    }
    else {
      nasp[i] = nasp[i - 1] + 1;
      for(int u = 0; u < 2; u++)
	dp[i][u][0] = min({nasp[i - 1] + 1, dp[i - 1][u][0], dp[i - 1][!u][1], dp[i - 1][u][1] + 1, dp[i - 1][!u][0] + 1}) + elems[i].c[u],
	dp[i][u][1] = min({nasp[i - 1] + 2, dp[i - 1][u][0] + 1, dp[i - 1][u][1]}) + elems[i].c[!u];
    }
    //for(int a = 0; a < 2; a++)
      //for(int b = 0; b < 2; b++)
	//cout << dp[i][a][b] << " \n"[b == 1];
    //cerr << nasp[i] << "\n--\n";
  }
  int mn = nasp[elems.size() - 1];
  for(int u = 0; u < 4; u++)
    mn = min(mn, dp[elems.size() - 1][u & 1][u >> 1]);
  cout << mn << '\n';
}

//13
//1010010010100
//0000111001011

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/


//001100010010000110
//110110001000100101

Compilation message

lamp.cpp: In function 'int main()':
lamp.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<box>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = 0; i < elems.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
lamp.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<box>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i = 1; i < elems.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
lamp.cpp:59:6: warning: statement has no effect [-Wunused-value]
   59 |  true;
      |      ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 44 ms 6208 KB Output is correct
8 Runtime error 81 ms 44468 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -