Submission #1118654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118654		vjudge1	Lamps (JOI19_lamps)	C++17	47 / 100	20 ms	9128 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

#define TASK "Lamps"
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

mt19937 rng(time(0));

const int N = (int)1e5 + 7;
int n;
string a, b;
int dp[N][3];

void Read()
{
    cin >> n >> a >> b;
}

int OP(int state, int op)
{
    if(op == 0)
        return state;
    if(op == 1)
        return 0;
    if(op == 2)
        return 1;
//    assert(false);
}

void Solve()
{
    for(auto& c : a) c -= '0';
    for(auto& c : b) c -= '0';
    n--;
    memset(dp, 0x3f, sizeof dp);
//    dp[0][0] = 0;
    FOR(i, 0, n)
    {
        FOR(pre, 0, 2)
        {
            FOR(cur, 0, 2)
            {
                int need;
                if(i == 0)
                    need = cur != 0;
                else
                    need = dp[i - 1][pre] + (pre != cur && cur != 0);
                if((i == 0 || OP(a[i - 1], pre) == b[i - 1]) && OP(a[i], cur) != b[i])
                    ++need;
                minimize(dp[i][cur], need);
            }
        }
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2]});
}

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    Read();
    Solve();

    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int OP(int, int)':
lamp.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^
lamp.cpp: In function 'int main()':
lamp.cpp:67:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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