Submission #1105130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105130		Zero_OP	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	142 ms	18156 KiB

linear_garden

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(name) if(fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

const int MAX = 1e6 + 5;

int n, mod;
string s;
int vec[MAX];
int minDiff[MAX], maxDiff[MAX], diff[MAX];

void add(int& a, int b){
    a += b;
    if(a >= mod) a -= mod;
}

void testcase(){
    cin >> n >> mod >> s;
    rep(i, 0, n) vec[i] = (s[i] == 'P'); //L < P

    int v[2] = {+1, -1};
    for(int i = 0, cur = 0; i < n; ++i){
        cur += v[vec[i]];
        diff[i] = cur;
        minDiff[i] = min(0, diff[i]);
        maxDiff[i] = max(0, diff[i]);
//        cout << cur << ' ';
    }
//    cout << '\n';

    rep(i, 1, n){
        minimize(minDiff[i], minDiff[i - 1]);
        maximize(maxDiff[i], maxDiff[i - 1]);
    }

    vector<vector<vector<int>>> f(5, vector<vector<int>>(3, vector<int>(3)));
    vector<vector<vector<int>>> g(5, vector<vector<int>>(3, vector<int>(3)));

    FOR(mn, -2, 0){
        FOR(mx, 0, +2){
            FOR(i, mn, mx){
                if(mx - mn <= 2){
                    f[i + 2][mn + 2][mx] = 1;
//                    cout << "init : " << i << ' ' << mn << ' ' << mx << '\n';
                }
            }
        }
    }

    auto fit = [&](int x){
        return 0 <= x && x <= 2;
    };

    auto fitCur = [&](int x){
        return 0 <= x && x <= 4;
    };

    int ans = 1;
    for(int i = n - 1; i >= 0; --i){
        if(vec[i] == 1){
            int ndiff = (i == 0 ? 0 : diff[i - 1]) + 1;
            int nmin = min(ndiff, (i == 0 ? 0 : minDiff[i - 1]));
            int nmax = max(ndiff, (i == 0 ? 0 : maxDiff[i - 1]));
//            cout << i << " : " << ndiff << ' ' << nmin << ' ' << nmax << '\n';
            if(nmax - nmin <= 2 && ndiff <= 2){
//                cout << "! " << ndiff << ' ' << dbg(nmin) << ' ' << nmax << '\n';
                assert(fitCur(ndiff + 2));
                assert(fit(nmin + 2));
                assert(fit(nmax));
//                exit(0);
//                cout << f[ndiff + 2][nmin + 2][nmax] << '\n';
                add(ans, f[ndiff + 2][nmin + 2][nmax]);
            }
        }

        FOR(mn, -2, 0){
            FOR(mx, 0, +2){
                FOR(cur, mn, mx){
//                    cout << cur + 2 << ' ' << mn + 2 << ' ' << mx << '\n';
                    assert(fitCur(cur + 2));
                    assert(fit(mn + 2));
                    assert(fit(mx));
                    g[cur + 2][mn + 2][mx] = f[cur + 2][mn + 2][mx];
                    f[cur + 2][mn + 2][mx] = 0;
                }
            }
        }

        FOR(mn, -2, 0){
            FOR(mx, 0, +2){
                FOR(cur, mn, mx){
                    if(cur < +2) { //place L
//                        cout << cur + 1 << ' ' << mn << ' ' << max(mx, cur + 1) << ' ' << dbg(g[cur + 2][mn + 2][mx]) << '\n';
                        add(f[cur + 2][mn + 2][mx], g[cur + 3][mn + 2][max(mx, cur + 1)]);
                    }

                    if(cur > -2) { //place P
//                        cout << cur - 1 << ' ' << min(mn, cur - 1) << ' ' << mx << ' ' << dbg(g[cur + 2][mn + 2][mx]) << '\n';
                        add(f[cur + 2][mn + 2][mx], g[cur + 1][min(mn, cur - 1) + 2][mx]);
                    }
                }
            }
        }
    }

    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("task");

    int T = 1; //cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'bool minimize(T&, const T&)':
linear_garden.cpp:16:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |     if(a > b) return a = b, true; return false;
      |     ^~
linear_garden.cpp:16:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
linear_garden.cpp: In function 'bool maximize(T&, const T&)':
linear_garden.cpp:21:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |     if(a < b) return a = b, true; return false;
      |     ^~
linear_garden.cpp:21:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:12:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define file(name) if(fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:139:5: note: in expansion of macro 'file'
  139 |     file("task");
      |     ^~~~
linear_garden.cpp:12:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define file(name) if(fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:139:5: note: in expansion of macro 'file'
  139 |     file("task");
      |     ^~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5