Submission #1199066

#TimeUsernameProblemLanguageResultExecution timeMemory
1199066_noobLinear Garden (IOI08_linear_garden)C++20
0 / 100
2 ms328 KiB
#pragma GCC optimize("Ofast") #include <iostream> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <set> #include <map> #include <deque> #include <stack> #include <queue> #include <algorithm> #include <cassert> #include <random> #include <chrono> #include <iomanip> #include <cmath> #include <bitset> #include <functional> #include <numeric> #define int long long #define double long double #define ii pair<int,int> #define iii pair<int, ii > #define fi first #define se second #define getbit(x,y) (((x)>>(y))&1ll) #define turnon(x,y) ((x)|(1ll<<y)) #define turnof(x,y) ((x)^(1ll<<y)) #define oo 1e18 #define pb push_back #define all(x) x.begin(),x.end() #define con(mask) mask=(mask-1)&mask #define Unique(val) val.erase(unique(val.begin(),val.end()),val.end()) #define ll long long #define rand_int mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rand_ll mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); const int mod = 1e9 + 7; const double pi = acos(-1); const int N = 450; const double esp = 1e-9; int base = 100000; using namespace std; int n, m; string s; int f[1000005]; void add(int &x, int y) { x += y; if(x >= m) x -= m; } void sub(int &x, int y) { x -= y; if(x < 0) x += m; } int dp[2][5][5][5][2]; // dp[i][sum][mx][mn][is_less] void sol_1() { dp[0][2][2][2][0] = 1; for(int i = 0; i < n; i++) { int nx = 1 - i % 2; int cur = i % 2; for(int sum = 0; sum <= 4; sum++) { for(int mx = 2; mx <= 4; mx++) { for(int mn = 0; mn <= 2; mn++) { for(int is_less = 0; is_less <= 1; is_less++) { int new_sum = sum + 1; int new_mx = max(mx, new_sum); int new_mn = min(mn, new_sum); if(new_mx - new_mn <= 2) { // set L add(dp[nx][new_sum][new_mx][new_mn][is_less || (s[i] == 'P')], dp[cur][sum][mx][mn][is_less]); } new_sum = sum - 1; new_mx = max(mx, new_sum); new_mn = min(mn, new_sum); if(new_mx - new_mn <= 2 && (is_less || (s[i] == 'P'))) { // set P add(dp[nx][new_sum][new_mx][new_mn][is_less], dp[cur][sum][mx][mn][is_less]); } } } } } memset(dp[cur], 0, sizeof(dp[cur])); } int ans = 0; for(int sum = 0; sum <= 4; sum++) { for(int mx = 2; mx <= 4; mx++) { for(int mn = 0; mn <= 2; mn++) { for(int is_less = 0; is_less <= 1; is_less++) { if(mx - mn <= 2) { add(ans, dp[n % 2][sum][mx][mn][is_less]); } } } } } cout << ans; } void sol_2() { f[0] = 1; for(int i = 1; i <= n; i++) f[i] = f[i - 1] * 2 % m; /* Có 3 TH có thể xảy ra: 1. Nếu đoạn mình đi trong đoạn 0 -> 2, xuất phát ở 0 => Bước chẵn có 2TH, còn lẻ chỉ có 1TH duy nhất 2. Nếu đoạn mình đi là -2 -> 0 => đối xứng với TH1 3. Nếu đoạn mình đi là -1 -> 1 => Bước lẻ có 2TH, còn chẵn chỉ có 1TH duy nhất */ int sum = 0, mx = 0, mn = 0; int res = 1; for(int i = 0; i < n; i++) { int len = n - i - 1; if(s[i] == 'P') { // set L int tmp = sum + 1; int new_mx = max(mx, tmp); int new_mn = mn; if(new_mx - new_mn == 2) { // Đã lấy 2 hàng => xét vị trí bắt đầu if(tmp == new_mx - 1) { add(res, f[(len + 1) / 2]); } else { add(res, f[len / 2]); } } else if(new_mx - new_mn == 1) { add(res, f[len / 2]); add(res, f[(len + 1) / 2]); sub(res, 1); } sum--; mn = min(mn, sum); } else { sum++; mx = max(mx, sum); } } cout << res; } void solve() { cin >> n >> m >> s; // sol_1(); sol_2(); } signed main() { #ifndef ONLINE_JUDGE freopen("inp.inp", "r", stdin); freopen("out.out", "w", stdout); #endif ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; //cin >> t; while(t--) { solve(); } } // ProTeam //(¯`·.·´¯) (¯`·.·´¯) //`·.¸(¯`·.·´¯)¸ .· //×°× ` ·.¸.·´ ×°×

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:177:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |     freopen("inp.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:178:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |     freopen("out.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...