Submission #1016500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016500		TgX_2	Linear Garden (IOI08_linear_garden)	C++17	0 / 100	45 ms	65536 KiB

linear_garden

/*-----------------------------
        Author : TgX.2
       11Ti - K28 - CHV
-----------------------------*/

#include <bits/stdc++.h> 

#define FOR(i, a, b)       for (__typeof(b) i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b)      for (__typeof(b) i = (a), _b = (b); i >= _b; i--)
#define FORC(i, a, b, c)   for (__typeof(b) i = (a), _b = (b), _c = (c); i <= _b; i += _c)
#define FORSq(i, a, b)     for (__typeof(b) i = (a), _b = (b); i * i <= _b; ++i)
#define FORSt(i, s)        for (int i = 0, _s = (int)(s.size()); i < _s; ++i)

#define fi                 first
#define se                 second
#define pb                 push_back
#define len(x)             (int)((x).size())
#define all(x)             (x).begin(), (x).end()

#define _                  << " " <<
#define __                 << "\n"
#define ___                << " "

#define file               "temp"
#define ______________TgX______________ main()
// #define int                long long
#define intmax             1e9
#define intmin            -1e9
#define llongmax           1e18
#define llongmin          -1e18
#define memo(a, val)       memset((a), (val), sizeof((a)))

using   namespace std;
typedef long long          ll;
typedef unsigned long long ull;
typedef pair<int, int>     pii;
typedef vector<int>        vi;
typedef vector<pii>        vpii;
#define arr(element_type, cnt) array<element_type, (cnt)>

#define db(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << "[ " << *it << " = " << a << " ] ";
    err(++it, args...);
}

template<typename T1, typename T2> ostream& operator << (ostream& out, const pair<T1, T2>& p) {
    return out << "[ " << p.first << " , " << p.second << " ] ";
}

template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator << (ostream& out, const Con& con) {
    out << "{ ";
    for (auto beg = con.begin(), it = beg; it != con.end(); it++) {
        out << (it == beg ? "" : ", ") << *it;
    }
    return out << " } ";
}

template<typename T1, typename T2> 
bool mini(T1 &a, T2 b)
    {if (a > b) a = b; else return 0; return 1;}

template<typename T1, typename T2> 
bool maxi(T1 &a, T2 b)
    {if (a < b) a = b; else return 0; return 1;}
/*-----------------------------*/

const int maxn = 1e6 + 7;

int f[maxn][5][5];
int n, m; string s;

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


int dp(int id, int a, int b) {
	// cout << id _ a _ b __ ;	
	if (a < -2 or b > 2) return 0;
	if (id > n) return 1;

	int &ans = f[id][abs(a)][b];
	if (ans != -1) return ans;

	ans = 0;
	add(ans, dp(id + 1, min({0, a - 1, -1}), max({0, b - 1, -1})));
    add(ans, dp(id + 1, min({0, a + 1, +1}), max({0, b + 1, +1})));
    return ans;
}

void process() {
	cin >> n >> m;
	memo(f, -1);
	int a = 0, b = 0, ans = 0;
	FOR(i, 1, n) {
		char x; cin >> x;
      	if (x == 'P'){
        	if (a != -2) 
        		add(ans, dp(i + 1, min({0, a - 1, -1}), max({0, b - 1, -1})));
         a = min({0, a + 1, +1});
         b = max({0, b + 1, +1});
      } else {
         a = min({0, a - 1, -1});
         b = max({0, b - 1, -1});
      }
	}

	cout << ans + 1;
}



/*-----------------------------*/
______________TgX______________ {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    if (fopen(file".inp", "r")) {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
        freopen(file".debug", "w", stderr);
    }
    process();
}


/*==============================+
|INPUT                          |
--------------------------------|

================================+
|OUTPUT                         |
--------------------------------|

===============================*/

Compilation message (stderr)

linear_garden.cpp:25:41: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | #define ______________TgX______________ main()
      |                                         ^~~~
linear_garden.cpp:120:1: note: in expansion of macro '______________TgX______________'
  120 | ______________TgX______________ {
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(file".debug", "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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