oj.uz

Submission #1070020

# Submission time Handle Problem Language Result Execution time Memory
1070020 2024-08-22T11:04:08 Z vjudge1 Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 17 ms 4564 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 {
       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(L[i] == -1) ans = max(ans, v[i].first - L[i]);
            else if(R[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 344 KB Correct
2 Correct 1 ms 348 KB Correct

Subtask #1
3.0 / 3.0

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

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 16 ms 4308 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 344 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 9 ms 600 KB Correct
4 Correct 1 ms 344 KB Correct
5 Correct 11 ms 348 KB Correct
6 Correct 11 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 10 ms 456 KB Correct
9 Correct 10 ms 456 KB Correct
10 Correct 10 ms 460 KB Correct
11 Correct 3 ms 348 KB Correct
12 Correct 10 ms 464 KB Correct
13 Correct 12 ms 344 KB Correct
14 Correct 1 ms 348 KB Correct
15 Correct 7 ms 460 KB Correct
16 Correct 8 ms 348 KB Correct
17 Correct 7 ms 348 KB Correct
18 Correct 10 ms 448 KB Correct
19 Correct 0 ms 348 KB Correct
20 Correct 0 ms 344 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 17 ms 4564 KB Incorrect string length
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

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