oj.uz

답안 #1045719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045719 2024-08-06T07:09:41 Z SamAnd Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 46 ms 12884 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005;

int n, m;
int s[N], f[N];

vector<pair<int, pair<int, int> > > v[N];
vector<int> vv[N];

int dp[N];
pair<pair<int, int>, pair<int, int> > p[N];
bool stg(int k)
{
    for (int i = 0; i <= n + 1; ++i)
    {
        dp[i] = 0;
        v[i].clear();
        vv[i].clear();
    }
    for (int i = 1; i < n; ++i)
    {
        if (s[i] + k <= s[i + 1] - k)
        {
            int l = s[i + 1] - k;
            int r = s[i] + k;

            int ri = i + 1;
            while (ri + 1 <= n && s[ri + 1] <= r)
            {
                ++ri;
                r = s[ri] + k;
            }

            int li = i;
            while (li - 1 >= 1 && s[li - 1] >= l)
            {
                --li;
                l = s[li] - k;
            }

            v[li].push_back(m_p(ri, m_p(l, r)));
            vv[li].push_back(i);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < sz(v[i + 1]); ++j)
        {
            int l = v[i + 1][j].se.fi;
            int r = v[i + 1][j].se.se;
            int x = dp[i] + 1;
            while (x <= m && l <= f[x] && f[x] <= r)
                ++x;
            if (x - 1 > dp[v[i + 1][j].fi])
            {
                dp[v[i + 1][j].fi] = x - 1;
                p[v[i + 1][j].fi] = m_p(m_p(i, vv[i + 1][j]), m_p(i + 1, v[i + 1][j].fi));
            }
        }
        {
            int l = s[i + 1];
            int r = s[i + 1] + k;
            int x = dp[i] + 1;
            while (x <= m && l <= f[x] && f[x] <= r)
                ++x;
            if (x - 1 > dp[i + 1])
            {
                dp[i + 1] = x - 1;
                p[i + 1] = m_p(m_p(i, i), m_p((i + 1), -(i + 1)));
            }
        }
        {
            int l = s[i + 1] - k;
            int r = s[i + 1];
            int x = dp[i] + 1;
            while (x <= m && l <= f[x] && f[x] <= r)
                ++x;
            if (x - 1 > dp[i + 1])
            {
                dp[i + 1] = x - 1;
                p[i + 1] = m_p(m_p(i, i), m_p(-(i + 1), (i + 1)));
            }
        }
    }

    return (dp[n] == m);
}

void solv()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> s[i];
    for (int i = 1; i <= m; ++i)
        cin >> f[i];

    int l = 0, r = 1000000009;
    int ans = -1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }

    cout << ans << "\n";
    if (ans != -1)
    {
        stg(ans);
        string s;
        s.assign(n + 1, '?');
        int i = n;
        while (i >= 1)
        {
            auto t = p[i];
            if (t.se.fi > 0 && t.se.se > 0)
            {
                int j = t.fi.se;
                s[j] = 'R';
                s[j + 1] = 'L';
                for (int k = j + 2; k <= t.se.se; ++k)
                    s[k] = 'R';
                for (int k = j - 1; k >= t.se.fi; --k)
                    s[k] = 'L';
            }
            else
            {
                if (t.se.fi < 0)
                {
                    s[t.se.se] = 'L';
                }
                else
                {
                    s[t.se.fi] = 'R';
                }
            }
            i = t.fi.fi;
        }
        reverse(all(s));
        s.pop_back();
        reverse(all(s));
        cout << s << "\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Correct
2 Correct 1 ms 6744 KB Correct

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Correct
2 Correct 6 ms 7984 KB Correct
3 Correct 1 ms 6744 KB Correct
4 Correct 7 ms 8236 KB Correct
5 Correct 10 ms 8284 KB Correct
6 Correct 1 ms 6744 KB Correct
7 Correct 1 ms 6748 KB Correct
8 Correct 2 ms 7004 KB Correct
9 Correct 1 ms 6748 KB Correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Correct
2 Correct 8 ms 8284 KB Correct
3 Correct 4 ms 7260 KB Correct
4 Correct 38 ms 9816 KB Correct
5 Correct 37 ms 9816 KB Correct
6 Correct 1 ms 7000 KB Correct
7 Correct 1 ms 6748 KB Correct
8 Correct 29 ms 9820 KB Correct
9 Correct 30 ms 9820 KB Correct
10 Correct 30 ms 9820 KB Correct
11 Correct 24 ms 8484 KB Correct
12 Correct 20 ms 8792 KB Correct
13 Correct 33 ms 9808 KB Correct
14 Correct 38 ms 10060 KB Correct
15 Correct 38 ms 10068 KB Correct
16 Correct 36 ms 12884 KB Correct

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Correct
2 Correct 1 ms 6744 KB Correct
3 Correct 1 ms 6748 KB Correct
4 Correct 1 ms 6960 KB Correct
5 Incorrect 1 ms 6748 KB User solution is worse than jury's solution
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Correct
2 Correct 14 ms 9052 KB Correct
3 Incorrect 46 ms 10328 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Correct
2 Correct 1 ms 6744 KB Correct
3 Correct 6 ms 7984 KB Correct
4 Correct 1 ms 6744 KB Correct
5 Correct 7 ms 8236 KB Correct
6 Correct 10 ms 8284 KB Correct
7 Correct 1 ms 6744 KB Correct
8 Correct 1 ms 6748 KB Correct
9 Correct 2 ms 7004 KB Correct
10 Correct 1 ms 6748 KB Correct
11 Correct 8 ms 8284 KB Correct
12 Correct 4 ms 7260 KB Correct
13 Correct 38 ms 9816 KB Correct
14 Correct 37 ms 9816 KB Correct
15 Correct 1 ms 7000 KB Correct
16 Correct 1 ms 6748 KB Correct
17 Correct 29 ms 9820 KB Correct
18 Correct 30 ms 9820 KB Correct
19 Correct 30 ms 9820 KB Correct
20 Correct 24 ms 8484 KB Correct
21 Correct 20 ms 8792 KB Correct
22 Correct 33 ms 9808 KB Correct
23 Correct 38 ms 10060 KB Correct
24 Correct 38 ms 10068 KB Correct
25 Correct 36 ms 12884 KB Correct
26 Correct 1 ms 6748 KB Correct
27 Correct 1 ms 6960 KB Correct
28 Incorrect 1 ms 6748 KB User solution is worse than jury's solution
29 Halted 0 ms 0 KB -