Submission #596230

#	Time	Username	Problem	Language	Result	Execution time	Memory
596230		spacewalker	Misspelling (JOI22_misspelling)	C++14	28 / 100	4054 ms	297916 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<vector<int>> firstIncEnds(n), firstDecEnds(n);
    for (int i = 0; i < m; ++i) {
        int a, b; scanf("%d %d", &a, &b); --a; --b;
        // a < b means first change is an increase
        if (a < b) firstDecEnds[a].push_back(b);
        else firstIncEnds[b].push_back(a);
    }
    // simplify the constraints
    for (int i = 0; i < n; ++i) {
        if (firstIncEnds[i].size() > 0) {
            firstIncEnds[i] = {*max_element(begin(firstIncEnds[i]), end(firstIncEnds[i]))};
        }
        if (firstDecEnds[i].size() > 0) {
            firstDecEnds[i] = {*max_element(begin(firstDecEnds[i]), end(firstDecEnds[i]))};
        }
        if (firstIncEnds[i].size() > 0 && firstDecEnds[i].size() > 0) {
            int first = min(firstIncEnds[i][0], firstDecEnds[i][0]), secnd = max(firstIncEnds[i][0], firstDecEnds[i][0]);
            if (first < secnd) {
                if (firstIncEnds[i][0] == secnd) firstIncEnds[first].push_back(secnd);
                if (firstDecEnds[i][0] == secnd) firstDecEnds[first].push_back(secnd);
                firstIncEnds[i][0] = firstDecEnds[i][0] = first;
            }
        }
    }
    vector<vector<ll>> lastInc(n, vector<ll>(26)), lastDec(n, vector<ll>(26));
    for (int i = 0; i < 26; ++i) lastInc[n-1][i] = 1;
    for (int i = n - 2; i >= 0; --i) {
        // count the current sols
        vector<ll> currEndAt(26);
        for (int j = i; j < n; ++j) {
            for (int d = 0; d < 26; ++d) {
                currEndAt[d] += lastInc[j][d] + lastDec[j][d];
                currEndAt[d] %= MOD;
            }
        }
        // update the counts for n
        for (int dnext = 0; dnext < 26; ++dnext) {
            for (int d = 0; d < 26; ++d) {
                if (d < dnext && firstDecEnds[i].size() == 0) { // increase
                    lastInc[i][d] += currEndAt[dnext];
                }
                if (d > dnext && firstIncEnds[i].size() == 0) { // decrease
                    lastDec[i][d] += currEndAt[dnext];
                }
            }
        }
        // eliminate all sols that don't follow any existing constraints
        if (firstIncEnds[i].size() > 0) {
            // printf("constraint first inc %d %d\n", i, firstIncEnds[i][0]);
            for (int d = 0; d < 26; ++d) {
                for (int j = i; j < firstIncEnds[i][0]; ++j) {
                    lastDec[j][d] = 0;
                }
            }
        }
        if (firstDecEnds[i].size() > 0) {
            // printf("constraint first dec %d %d\n", i, firstDecEnds[i][0]);
            for (int d = 0; d < 26; ++d) {
                for (int j = i; j < firstDecEnds[i][0]; ++j) {
                    lastInc[j][d] = 0;
                }
            }
        }
        for (int d = 0; d < 26; ++d) {
            // printf("%d %d inc %lld dec %lld\n", i, d, lastInc[i][d], lastDec[i][d]);
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int d = 0; d < 26; ++d) {
            ans = (ans + lastInc[i][d] + lastDec[i][d]) % MOD;
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
misspelling.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         int a, b; scanf("%d %d", &a, &b); --a; --b;
      |                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11