Submission #263632

#TimeUsernameProblemLanguageResultExecution timeMemory
263632NucleistLinear Garden (IOI08_linear_garden)C++14
55 / 100
508 ms65540 KiB
//Self-control leads to consistency. #include <bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll int #define INF 1000000000 #define MOD 1000000007 #define pb push_back #define ve vector<ll> #define dos pair<ll,ll> #define vedos vector<dos> #define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define EPS 0.000001 struct greateri { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } int n,m; map<pair<dos,dos>,int>dp; ve hed; int ans=0,ans1; int solve(int index,int high,int low,int cur){ } int main() { //flash; cin>>n; cin>>m; string in; cin>>in; int dif=0; int low=0; int high=0; int rank=0; for (int index = n-1; index >= 0; index--) { for (int high = -2; high <= 2; ++high) { for (int low = -2; low <= 2; ++low) { for (int cur = -2; cur <= 2; ++cur) { int ans=0; if(index==n-1){dp[{{index,high},{low,cur}}]=1;continue;} if(abs(cur-high+1)<=2 && abs(cur-low+1)<=2 && abs(cur+1)<=2){ int sol=cur+1; ans=(ans+dp[{{index+1,max(high,sol)},{min(low,sol),sol}}])%m; } if(abs(cur-high-1)<=2 && abs(cur-low-1)<=2 && abs(cur-1)<=2){ int sol=cur-1; ans=(ans+dp[{{index+1,max(high,sol)},{min(low,sol),sol}}])%m; } dp[{{index,high},{low,cur}}]=ans; } } } } for (int i = 0; i < sz(in); ++i) { if(in[i]=='P' && abs(dif-high+1)<=2 && abs(dif-low+1)<=2 && abs(dif+1)<=2){ rank=(rank+dp[{{i,max(high,dif+1)},{min(low,dif+1),dif+1}}])%m; } if(in[i]=='L'){ dif++; high=max(high,dif); low=min(low,dif); } else { dif--; low=min(low,dif); high=max(high,dif); } } cout<<(rank+1)%m; return 0; }

Compilation message (stderr)

linear_garden.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
linear_garden.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
linear_garden.cpp: In function 'int solve(int, int, int, int)':
linear_garden.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
   37 | }
      | ^
linear_garden.cpp: In function 'void setIO(std::string)':
linear_garden.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   freopen((s+".out").c_str(),"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...