Submission #472652

#	Time	Username	Problem	Language	Result	Execution time	Memory
472652		ITO	Lamps (JOI19_lamps)	C++11	100 / 100	322 ms	67068 KiB

lamp

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
string s1, s2, sa[16] = {"", "0", "1", "f", "01", "0f", "10", "1f", "f0", "f1", "01f", "0f1", "10f", "1f0", "f01", "f10"};
int a[1000001][16];
struct lol {
    string s;
    int t, c[16];
} la[16];
lol nom(string ss) {
    lol tm;
    tm.s = ss;
    tm.t = 3;
    for (char cc : ss) {
        if (cc == '0') {
            tm.t = 0;
        } else if (cc == '1') {
            tm.t = 1;
        } else {
            if (tm.t < 2) {
                tm.t = 1 - tm.t;
            } else {
                tm.t = 2;
            }
        }
    }
    for (int i = 0; i < 16; i++) {
        int k = 0;
        tm.c[i] = ss.length();
        for (int jj = 0; jj < ss.length(); jj++) {
            for (int kk = k; kk < sa[i].length(); kk++) {
                if (ss[jj] == sa[i][kk]) {
                    tm.c[i]--;
                    k = kk + 1;
                    break;
                }
            }
        }
    }
    return tm;
}
int main() {
    int n;
    cin >> n >> s1 >> s2;
    for (int i = 0; i < 16; i++) {
        la[i] = nom(sa[i]);
        a[0][i] = 10000000;
    }
    a[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 16; j++) {
            a[i + 1][j] = 10000000;
            if ((la[j].t == 3 && s1[i] == s2[i]) || (la[j].t == 2 && s1[i] != s2[i]) || (la[j].t == s2[i] - '0')) {
                for (int k = 0; k < 16; k++) {
                    a[i + 1][j] = min(a[i + 1][j], a[i][k] + la[j].c[k]);
                }
            }
        }
    }
    int co = 10000000;
    for (int i = 0; i < 16; i++) {
        co = min(co, a[n][i]);
    }
    cout << co << '\n';
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'lol nom(std::string)':
lamp.cpp:31:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int jj = 0; jj < ss.length(); jj++) {
      |                          ~~~^~~~~~~~~~~~~
lamp.cpp:32:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int kk = k; kk < sa[i].length(); kk++) {
      |                              ~~~^~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49