oj.uz

Submission #1045894

# Submission time Handle Problem Language Result Execution time Memory
1045894 2024-08-06T08:22:58 Z VahanAbraham Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 12636 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 200005;
const ll oo = 100000000000000000, MOD = 1000000007;

int n, m;
vector<int> vec[3], qc[N];
ll leftuj[N], rightuj[N], pat = oo;
char num[N];
vector<int> l_er, r_er;
ll s[N], f[N];

void rec(int ind) {
    qc[0].pb(ind);
    vec[0].pb(s[ind]);
    if (ind != n) {
        rec(ind + 1);
    }
    else {
        int last0 = 0, last1 = vec[1].size() - 1;
        for (int i = 1; i <= m; ++i) {
            leftuj[i] = oo;
            while (last0 < vec[0].size() && vec[0][last0] < f[i]) {
                ++last0;
            }
            if (last0 < vec[0].size()) {
                leftuj[i] = vec[0][last0] - f[i];
            }
        }
        for (int i = m; i >= 1; --i) {
            rightuj[i] = oo;
            while (last1 >= 0 && vec[1][last1] > f[i]) {
                --last1;
            }
            if (last1 >= 0) {
                rightuj[i] = f[i] - vec[1][last1];
            }
        }
        ll ans = 0;
        for (int i = 1; i <= m; ++i) {
            ans = max(ans, min(leftuj[i], rightuj[i]));
        }
        if (ans < pat) {
            pat = ans;
            l_er = qc[0];
            r_er = qc[1];
        }
    }
    qc[0].pop_back();
    vec[0].pop_back();
    vec[1].pb(s[ind]);
    qc[1].pb(ind);
    if (ind != n) {
        rec(ind + 1);
    }
    else {
        int last0 = 0, last1 = vec[1].size() - 1;
        for (int i = 1; i <= m; ++i) {
            leftuj[i] = oo;
            while (last0 < vec[0].size() && vec[0][last0] < f[i]) {
                ++last0;
            }
            if (last0 < vec[0].size()) {
                leftuj[i] = vec[0][last0] - f[i];
            }
        }
        for (int i = m; i >= 1; --i) {
            rightuj[i] = oo;
            while (last1 >= 0 && vec[1][last1] > f[i]) {
                --last1;
            }
            if (last1 >= 0) {
                rightuj[i] = f[i] - vec[1][last1];
            }
        }
        ll ans = 0;
        for (int i = 1; i <= m; ++i) {
            ans = max(ans, min(leftuj[i], rightuj[i]));
        }
        if (ans < pat) {
            pat = ans;
            l_er = qc[0];
            r_er = qc[1];
        }
    }
    qc[1].pop_back();
    vec[1].pop_back();
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> f[i];
    }
    rec(1);
    if (pat == oo) {
        cout << -1 << endl;
        return;
    }
    cout << pat << endl;
    for (int i = 0; i < l_er.size(); ++i) {
        num[l_er[i]] = 'L';
    }
    for (int i = 0; i < r_er.size(); ++i) {
        num[r_er[i]] = 'R';
    }
    for (int i = 1; i <= n; ++i) {
        cout << num[i];
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

Main.cpp: In function 'void rec(int)':
Main.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while (last0 < vec[0].size() && vec[0][last0] < f[i]) {
      |                    ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if (last0 < vec[0].size()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while (last0 < vec[0].size() && vec[0][last0] < f[i]) {
      |                    ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             if (last0 < vec[0].size()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int i = 0; i < l_er.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int i = 0; i < r_er.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 11356 KB Correct
2 Correct 7 ms 11612 KB Correct
3 Correct 2 ms 11356 KB Correct
4 Correct 12 ms 11612 KB Correct
5 Correct 8 ms 11612 KB Correct
6 Correct 1 ms 11352 KB Correct
7 Correct 2 ms 11356 KB Correct
8 Correct 3 ms 11448 KB Correct
9 Correct 1 ms 11356 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Correct
2 Execution timed out 2070 ms 11612 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Correct
2 Correct 1 ms 11356 KB Correct
3 Correct 3 ms 11356 KB Correct
4 Correct 2 ms 11356 KB Correct
5 Correct 4 ms 11356 KB Correct
6 Correct 6 ms 11356 KB Correct
7 Correct 2 ms 11356 KB Correct
8 Correct 5 ms 11356 KB Correct
9 Correct 7 ms 11356 KB Correct
10 Correct 4 ms 11456 KB Correct
11 Correct 2 ms 11356 KB Correct
12 Correct 5 ms 11452 KB Correct
13 Correct 8 ms 11356 KB Correct
14 Correct 2 ms 11356 KB Correct
15 Correct 4 ms 11356 KB Correct
16 Correct 3 ms 11356 KB Correct
17 Correct 3 ms 11356 KB Correct
18 Correct 3 ms 11412 KB Correct
19 Correct 2 ms 11356 KB Correct
20 Correct 1 ms 11356 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Correct
2 Execution timed out 2081 ms 12636 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Correct
2 Correct 1 ms 11356 KB Correct
3 Correct 7 ms 11612 KB Correct
4 Correct 2 ms 11356 KB Correct
5 Correct 12 ms 11612 KB Correct
6 Correct 8 ms 11612 KB Correct
7 Correct 1 ms 11352 KB Correct
8 Correct 2 ms 11356 KB Correct
9 Correct 3 ms 11448 KB Correct
10 Correct 1 ms 11356 KB Correct
11 Execution timed out 2070 ms 11612 KB Time limit exceeded
12 Halted 0 ms 0 KB -