# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1070185 | 2024-08-22T12:08:57 Z | YassineBenYounes | Sprinklers (CEOI24_sprinklers) | C++17 | 2000 ms | 2260 KB |
#include <bits/stdc++.h> using namespace std; void init(){ #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE } typedef long long ll; #define vi vector<int> #define pii pair<int, int > #define vii vector<pii> #define ff first #define ss second #define pb push_back #define int ll const int mx = 1e5+5; int n, m; vi s, f; bool dp[mx][2]; bool check(int k){ if(f[0] < s[0]){ dp[0][0] = 0; } else{ dp[0][0] = 1; } int cur = s[0]-k; if(f[0] < cur)dp[0][1] = 0; else dp[0][1] = 1; for(int i = 1; i < n;i++){ /// go front bool worse = 0; for(int x : f){ if(x > s[i-1] && x < s[i]){worse=1;break;} } if(worse){ dp[i][0] = 0; } else{ dp[i][0] |= dp[i-1][1]; dp[i][0] |= dp[i-1][0]; } //// go back worse = 0; for(int x : f){ if(x > s[i-1] && x < (s[i] - k)){worse=1;break;} } if(worse){ bool can = 1; for(int x : f){ if(x > (s[i-1]+k) && x < (s[i] - k)){can = 0;break;} } if(can){ dp[i][1] |= dp[i-1][1]; } else{ dp[i][1] = 0; } } else{ dp[i][1] |= dp[i-1][0]; dp[i][1] |= dp[i-1][1]; } } if(f[m-1] > s[n-1]){ if(f[m-1] > (s[n-1]+k))return 0; else{ return dp[n-1][0]; } } else{ return (dp[n-1][0] | dp[n-1][1]); } } string res; void construct(int k){ if(f[0] < s[0]){ dp[0][0] = 0; } else{ dp[0][0] = 1; } int cur = s[0]-k; if(f[0] < cur)dp[0][1] = 0; else dp[0][1] = 1; for(int i = 1; i < n;i++){ /// go front bool worse = 0; for(int x : f){ if(x > s[i-1] && x < s[i]){worse=1;break;} } if(worse){ dp[i][0] = 0; } else{ dp[i][0] |= dp[i-1][1]; dp[i][0] |= dp[i-1][0]; } //// go back worse = 0; for(int x : f){ if(x > s[i-1] && x < (s[i] - k)){worse=1;break;} } if(worse){ bool can = 1; for(int x : f){ if(x > (s[i-1]+k) && x < (s[i] - k)){can = 0;break;} } if(can){ dp[i][1] |= dp[i-1][1]; } else{ dp[i][1] = 0; } } else{ dp[i][1] |= dp[i-1][0]; dp[i][1] |= dp[i-1][1]; } } if(f[m-1] <= s[n-1]){ res[n-1] = 'L'; } else{ res[n-1] = 'R'; } for(int i = n-2; i >= 0;i--){ int big = s[i+1]; if(res[i+1] == 'L'){ big -= k; } bool can = 1; for(int x : f){ if(x > s[i] && x < (big)){can = 0;break;} } if(can){ res[i] = 'L'; } else{ res[i] = 'R'; } } } int32_t main(){ cin >> n >> m; for(int i = 0; i < n;i++){ int a;cin >> a; s.pb(a); } for(int i = 0; i < m;i++){ int a;cin >> a; f.pb(a); } int l = 0, r = 1e9; int ans = -1; while(l <= r){ int md = (l+r)/2; bool x = check(md); if(x){ ans = md; r = md-1; } else{ l = md+1; } } cout << ans << endl; if(ans != -1){ res.resize(n, ' '); construct(ans); cout << res << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Correct |
2 | Correct | 1 ms | 348 KB | Correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Correct |
2 | Correct | 26 ms | 1412 KB | Correct |
3 | Correct | 0 ms | 348 KB | Correct |
4 | Correct | 27 ms | 2148 KB | Correct |
5 | Correct | 27 ms | 2260 KB | Correct |
6 | Correct | 1 ms | 344 KB | Correct |
7 | Correct | 0 ms | 348 KB | Correct |
8 | Correct | 5 ms | 860 KB | Correct |
9 | Correct | 0 ms | 344 KB | Correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Correct |
2 | Execution timed out | 2062 ms | 1488 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Correct |
2 | Correct | 1 ms | 348 KB | Correct |
3 | Correct | 1 ms | 348 KB | Correct |
4 | Incorrect | 0 ms | 348 KB | User solution is incorrect |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Correct |
2 | Execution timed out | 2044 ms | 1484 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Correct |
2 | Correct | 1 ms | 348 KB | Correct |
3 | Correct | 26 ms | 1412 KB | Correct |
4 | Correct | 0 ms | 348 KB | Correct |
5 | Correct | 27 ms | 2148 KB | Correct |
6 | Correct | 27 ms | 2260 KB | Correct |
7 | Correct | 1 ms | 344 KB | Correct |
8 | Correct | 0 ms | 348 KB | Correct |
9 | Correct | 5 ms | 860 KB | Correct |
10 | Correct | 0 ms | 344 KB | Correct |
11 | Execution timed out | 2062 ms | 1488 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |