Submission #1070172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070172		vjudge1	Sprinklers (CEOI24_sprinklers)	C++17	26 / 100	40 ms	10180 KiB

Main

#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]!=s[3*i+1] or s[3*i]!=s[3*i+2]) 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
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47