oj.uz

Submission #1070165

# Submission time Handle Problem Language Result Execution time Memory
1070165 2024-08-22T12:03:36 Z vjudge1 Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 15 ms 1880 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve() {
   int n, m;
   cin >> n >> m;
   int s[n], f[m];
   for(int i=0; i<n; ++i) cin >> s[i];
   for(int i=0; i<m; ++i) cin >> f[i];
   if(n == 1) {
        if(f[0] < s[0] && f[m-1] > s[0]) {
            cout << -1 << endl;
            return;
        }
        cout << max(abs(f[0]-s[0]), abs(f[m-1]-s[0])) << endl;
        if(f[0] < s[0]) cout << "L" << endl;
        else cout << "R" << endl;
   } else if(n <= 10 && m <= 1000) {
       string ans = "";
       int cur = -1;
       for(int i=0; i<(1LL<<n); ++i) {
            string tmp = "";
            int cnt = 0;
            for(int j=0; j<n; ++j) {
                if((1LL<<j)&i) tmp += "R";
                else tmp += "L";
            }
            for(int j=0; j<m; ++j) {
                bool found = 0;
                int tmp2 = INT_MAX;
                for(int k=0; k<n; ++k) {
                    if(s[k] >= f[j] && tmp[k] == 'L') {
                        tmp2 = min(tmp2, s[k] - f[j]);
                        found = 1;
                        break;
                    }
                }
                for(int k=n-1; k>=0; --k) {
                    if(s[k] <= f[j] && tmp[k] == 'R') {
                        tmp2 = min(tmp2, f[j] - s[k]);
                        found = 1;
                        break;
                    }
                }
                if(!found) {
                    cnt = -1;
                    break;
                } else cnt = max(cnt, tmp2);
            }
            if(cnt != -1) {
                if(cur == -1 or cnt < cur) {
                    cur = cnt;
                    ans = tmp;
                }
            }
       }
       if(cur == -1) cout << cur << endl;
       else cout << cur << endl << ans << endl;
   } else {
       bool tc = 1;
       if(n%3==0) {
            for(int i=0; i<n/3; ++i) {
                if(s[3*i+1]!=s[3*i+2] or s[3*i+1]!=s[3*i+3]) tc = 0;
            }
       } else tc = 0;
       if(!tc) { // k <= 8
           for(int k=0; k<=8; ++k) {
               bool imp = 0;
               int last = 0, R = -1, L = -1;
               vector<char>ans(n, 'L');
               for(int i=0; i<m; ++i) {
                    if(f[i] <= R or L >= f[i]) continue;
                    if(last == n) {
                        imp = 1;
                        break;
                    }
                    while(last<n && s[last]+k < f[i]) ++last;
                    if(last == n) {
                        imp = 1;
                        break;
                    }
                    if(s[last] <= f[i]) {
                        ans[last] = 'R';
                        R = s[last] + k;
                    } else if((s[last] - k) > f[i]) {
                        imp = 1;
                        break;
                    } else L = s[last];
                    ++last;
                }
                if(imp) continue;
                cout << k << endl;
                for(int i=0; i<n; ++i) cout << ans[i];
                cout << endl;
                return;
            }
            cout << -1 << endl;
            return;
        }
       vector<pair<int,bool>>v;
       for(int i=0; i<n; ++i) v.push_back({s[i], 1});
       for(int i=0; i<m; ++i) v.push_back({f[i], 0});
       sort(v.begin(), v.end());
       int ans = 0, prev = -1;
       vector<int>L(n+m, -1), R(n+m, -1);
       for(int i=0; i<n+m; ++i) {
            if(v[i].second) prev = v[i].first;
            else L[i] = prev;
       }
       prev = -1;
       for(int i=n+m-1; i>=0; --i) {
            if(v[i].second) prev = v[i].first;
            else R[i] = prev;
       }
       for(int i=0; i<n+m; ++i) {
            if(v[i].second) continue;
            if(L[i] == -1 && R[i] == -1) {
                cout << -1 << endl;
                return;
            }
            if(R[i] == -1) ans = max(ans, v[i].first - L[i]);
            else if(L[i] == -1) ans = max(ans, R[i] - v[i].first);
            else ans = max(ans, min(v[i].first - L[i], R[i] - v[i].first));
       }
       cout << ans << endl;
       for(int i=0; i<n; i+=3) cout << "LLR";
       cout << endl;
   }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 6 ms 1100 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 7 ms 1236 KB Correct
5 Correct 7 ms 1116 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 2 ms 604 KB Correct
9 Correct 1 ms 600 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Incorrect 12 ms 1372 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 6 ms 348 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 11 ms 464 KB Correct
6 Correct 12 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 10 ms 460 KB Correct
9 Correct 10 ms 460 KB Correct
10 Correct 10 ms 348 KB Correct
11 Correct 1 ms 348 KB Correct
12 Correct 11 ms 460 KB Correct
13 Correct 11 ms 348 KB Correct
14 Correct 1 ms 348 KB Correct
15 Correct 8 ms 348 KB Correct
16 Correct 7 ms 348 KB Correct
17 Correct 7 ms 348 KB Correct
18 Correct 7 ms 452 KB Correct
19 Correct 0 ms 348 KB Correct
20 Correct 0 ms 348 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 8 ms 1116 KB Correct
3 Incorrect 15 ms 1880 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 6 ms 1100 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 7 ms 1236 KB Correct
6 Correct 7 ms 1116 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 2 ms 604 KB Correct
10 Correct 1 ms 600 KB Correct
11 Incorrect 12 ms 1372 KB User solution is worse than jury's solution
12 Halted 0 ms 0 KB -