Submission #311695

#	Time	Username	Problem	Language	Result	Execution time	Memory
311695		freerice	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	309 ms	14236 KiB

linear_garden

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
typedef pair<pair<int, int>, int> ppi;
typedef pair<int, pair<int, int> > pip;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int, int> > vpi;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define endl '\n'

#define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
#define FORd(i, a, b) for (int (i) = (a); i >= (b); --i)
#define TRAV(i, x) for (auto& (i) : (x))
#define PRSP(x, a) for (int rv = 0; rv < a; ++rv) {cout << ((rv==0 ? "" : " ")) << x[rv];} cout << endl;
#define mppi(a, b, c) mp(mp((a), (b)), (c))
#define mpip(a, b, c) mp((a), mp((b), (c)))
#define max3(a, b, c) max(max((a), (b)), (c))
#define min3(a, b, c) min(min((a), (b)), (c))

void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	if (name == "")
        return;
    if (name == "input") {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }
	else {
        freopen((name+".in").c_str(),"r",stdin);
        freopen((name+".out").c_str(),"w",stdout);
    }
}

const int INF = INT_MAX;
const int NINF = INT_MIN;
const int MAXLOG = 21;
const int MAXSEG = (1<<18);
const int MUL = 1000001;
const int MOD = 1000000007;
const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    ll operator()(ll x) const {
        return x ^ RANDOM;
    }
};

const int N = 1000005;

int n, m;
string s;
int dp[40][2];
int comp[5][5][5];
int mi_arr[N], ma_arr[N], cur_arr[N];

int main() {
	chrono::high_resolution_clock::time_point t0 = chrono::high_resolution_clock::now();

	setIO();
    cin >> n >> m;
    cin >> s;
    int cnt = 0;
    FOR (i, 0, 5) {
        FOR (j, 0, 5) {
            FOR (k, 0, 5) {
                comp[i][j][k] = 39;
                if (i > j)
                    continue;
                if (k >= i && k <= j) {
                    comp[i][j][k] = cnt++;
                }
            }
        }
    }
    // cout << cnt << '\n';
    int ans = 1;
    int mi = 2, ma = 2, cur = 2;
    FOR (i, 0, s.size()) {
        mi_arr[i] = mi;
        ma_arr[i] = ma;
        cur_arr[i] = cur;
        cur += (s[i]=='L') ? 1 : -1;
        mi = min(mi, cur);
        ma = max(ma, cur);
    }
    FORd (l, n, 0) {
        FOR (i, 0, 5) {
            FOR (j, 0, 5) {
                if (j < i)
                    continue;
                FOR (k, 0, 5) {
                    if (k > j || k < i) {
                        continue;
                    }
                    int ind = comp[i][j][k];
                    dp[ind][l%2] = 0;
                    if (l == n) {
                        dp[ind][l%2] = 1;
                    }
                    else {
                        if (k+1 <= j)
                            dp[ind][l%2] = (dp[ind][l%2] + dp[comp[i][j][k+1]][(l+1)%2]) % m;
                        if (k-1 >= i)
                            dp[ind][l%2] = (dp[ind][l%2] + dp[comp[i][j][k-1]][(l+1)%2]) % m;
                    }
                }
            }
        }
        /*cout << l << '\n';
        FOR (i, 0, 5) {
            FOR (j, 0, 5) {
                FOR (k, 0, 5) {
                    cout << dp[comp[i][j][k]][l%2] << " ";
                }
                cout << '\n';
            }
            cout << '\n';
        }
        cout << '\n';*/
        if (l != n && s[l] == 'P') {
            mi = mi_arr[l];
            ma = ma_arr[l];
            cur = cur_arr[l];
            if (ma - mi == 2)
                ans += dp[comp[mi][ma][cur+1]][(l+1)%2];
            else if (ma - mi == 1) {
                ans += dp[comp[mi-1][ma][cur+1]][(l+1)%2] + dp[comp[mi][ma+1][cur+1]][(l+1)%2];
                ans -= dp[comp[mi][ma][cur+1]][(l+1)%2];
            }
            else if (ma - mi == 0) {
                ans += dp[comp[mi-2][ma][cur+1]][(l+1)%2] + dp[comp[mi-1][ma+1][cur+1]][(l+1)%2] + dp[comp[mi][ma+2][cur+1]][(l+1)%2];
                ans -= dp[comp[mi-1][ma][cur+1]][(l+1)%2] + dp[comp[mi][ma+1][cur+1]][(l+1)%2];
                ans += dp[comp[mi][ma][cur+1]][(l+1)%2];
            }
            ans = ans % m;
        }
        // cout << ans << '\n';
    }
    cout << ans % m << '\n';

	chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
//	cout << "TIME: " << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << " ms" << endl;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:80:5: note: in expansion of macro 'FOR'
   80 |     FOR (i, 0, 5) {
      |     ^~~
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:81:9: note: in expansion of macro 'FOR'
   81 |         FOR (j, 0, 5) {
      |         ^~~
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:82:13: note: in expansion of macro 'FOR'
   82 |             FOR (k, 0, 5) {
      |             ^~~
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR (i, 0, s.size()) {
      |     ^~~
linear_garden.cpp:28:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                                            ^
linear_garden.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR (i, 0, s.size()) {
      |     ^~~
linear_garden.cpp:29:32: warning: unnecessary parentheses in declaration of 'l' [-Wparentheses]
   29 | #define FORd(i, a, b) for (int (i) = (a); i >= (b); --i)
      |                                ^
linear_garden.cpp:103:5: note: in expansion of macro 'FORd'
  103 |     FORd (l, n, 0) {
      |     ^~~~
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:104:9: note: in expansion of macro 'FOR'
  104 |         FOR (i, 0, 5) {
      |         ^~~
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:105:13: note: in expansion of macro 'FOR'
  105 |             FOR (j, 0, 5) {
      |             ^~~
linear_garden.cpp:28:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   28 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
linear_garden.cpp:108:17: note: in expansion of macro 'FOR'
  108 |                 FOR (k, 0, 5) {
      |                 ^~~
linear_garden.cpp:74:44: warning: variable 't0' set but not used [-Wunused-but-set-variable]
   74 |  chrono::high_resolution_clock::time_point t0 = chrono::high_resolution_clock::now();
      |                                            ^~
linear_garden.cpp:158:44: warning: variable 't1' set but not used [-Wunused-but-set-variable]
  158 |  chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
      |                                            ^~
linear_garden.cpp: In function 'void setIO(std::string)':
linear_garden.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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