oj.uz

Submission #1070031

# Submission time Handle Problem Language Result Execution time Memory
1070031 2024-08-22T11:09:48 Z vjudge1 Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 169 ms 5364 KB 
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pii pair<int,int>
pii bad = {-1,-1};
const int jonkler = 1e15;
signed main() {
    int n,m;
    cin >> n >> m;
    vector<int> a(n),b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < m; i++)
        cin >> b[i];

    auto solve = [&](int k)
    {
        queue<pii> all;
        int i = 0,  j = 0;
        while(i < n && j < m)
        {
            if (a[i] < b[j])
                all.push({a[i++],1});
            else
                all.push({b[j++],0});
        }
       while (i<n) all.push({a[i++],1});
        while (j<m) all.push({b[j++],0});
        int prev = jonkler;
        int range = -1;
       
        while (all.size())
        {
            auto cur = all.front();
            if (cur.ss)
            {
                if (prev == jonkler)
                range = cur.ff+k;
                else
                {
                    if (prev < cur.ff - k)
                    {
                        return 0;
                    }
                    else
                        prev = jonkler;
                }
            }
            else
            {
                if (cur.ff>range)
                prev = min(prev,cur.ff);
            }
            all.pop();
        }
        if (prev > range && prev != jonkler)
            return 0;
        return 1;
    };
    int l = 0, r = 1e10;
    while(r-l>1)
    {
        int mid = l+r>>1;
        if (solve(mid))
            r = mid;
        else
            l = mid;
    }
    string ans;
    auto fillstr = [&](int k)
    {
        queue<pii> all;
        int i = 0,  j = 0;
        while(i < n && j < m)
        {
            if (a[i] < b[j])
                all.push({a[i++],1});
            else
                all.push({b[j++],0});
        }
       while (i<n) all.push({a[i++],1});
        while (j<m) all.push({b[j++],0});
        int prev = jonkler;
        int range = -1;
       
        while (all.size())
        {
            auto cur = all.front();
            if (cur.ss)
            {
                if (prev == jonkler)
                {
                    range = cur.ff+k;
                    ans.push_back('R');
                }
                else
                {
                    
                    prev = jonkler;
                    ans.push_back('L');
                }
            }
            else
            {
                if (cur.ff>range)
                prev = min(prev,cur.ff);
            }
            all.pop();
        }
        
    };
    if (r == 1e10)
        cout << "-1\n";
    else
    {
    if (solve(l))
    {
        cout << l << '\n';
        fillstr(l);
        cout << ans << '\n';
      
    }
    else
    {
        cout << r << '\n';
        fillstr(r);
         cout << ans << '\n';
    }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid = l+r>>1;
      |                   ~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 3.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 74 ms 2948 KB Correct
3 Correct 11 ms 784 KB Correct
4 Correct 162 ms 5316 KB Correct
5 Correct 162 ms 5304 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 151 ms 5304 KB Correct
9 Correct 149 ms 5312 KB Correct
10 Correct 169 ms 5364 KB Correct
11 Correct 80 ms 2940 KB Correct
12 Correct 107 ms 3576 KB Correct
13 Correct 131 ms 4532 KB Correct
14 Correct 127 ms 4528 KB Correct
15 Correct 128 ms 4476 KB Correct
16 Correct 128 ms 4488 KB Correct

Subtask #3
0.0 / 17.0

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

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 84 ms 3176 KB User solution is worse than jury's solution
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 0 ms 348 KB Correct
3 Correct 62 ms 2444 KB Correct
4 Incorrect 0 ms 348 KB User solution is worse than jury's solution
5 Halted 0 ms 0 KB -