Submission #1045894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045894		VahanAbraham	Sprinklers (CEOI24_sprinklers)	C++17	20 / 100	2081 ms	12636 KiB

Main

#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 (stderr)

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
• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47