Submission #1046086

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046086	2024-08-06T09:53:38 Z	Mher777	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	16 ms	1336 KB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937_64 rnd(7069);

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);

/* -------------------- Constants -------------------- */

const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

/* -------------------- Functions -------------------- */

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

void precision(int x) {
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}

ll gcd(ll a, ll b) {
    if (a == 0 || b == 0) return(max(a, b));
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll range_sum(ll a, ll b) {
    if (a > b) return 0ll;
    ll dif = a - 1, cnt = b - a + 1;
    ll ans = ((b - a + 1) * (b - a + 2)) / 2;
    ans += ((b - a + 1) * dif);
    return ans;
}

string dec_to_bin(ll a) {
    string s = "";
    for (ll i = a; i > 0; ) {
        ll k = i % 2;
        i /= 2;
        char c = k + 48;
        s += c;
    }
    if (a == 0) {
        s = "0";
    }
    reverse(all(s));
    return s;
}

ll bin_to_dec(string s) {
    ll num = 0;
    for (int i = 0; i < s.size(); i++) {
        num *= 2ll;
        num += (s[i] - '0');
    }
    return num;
}

ll factorial_by_mod(ll n, ll mod) {
    ll ans = 1;
    ll num;
    for (ll i = 1; i <= n; ++i) {
        num = i % mod;
        ans *= num;
        ans %= mod;
    }
    return ans;
}

bool isPrime(ll a) {
    if (a == 1) return false;
    for (ll i = 2; i * i <= a; i++) {
        if (a % i == 0) return false;
    }
    return true;
}

ll binpow(ll a, ll b) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return ans;
}

/* -------------------- Solution -------------------- */

const int N = 100005;
int n, m;

void slv() {
    cin >> n >> m;
    vi 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[m] > s[1] && f[1] < s[1]) {
            cout << -1;
            return;
        }
        cout << max(abs(f[m] - s[1]), abs(f[1] - s[1])) << '\n';
        if (f[m] > s[1]) {
            cout << "R";
            return;
        }
        cout << "L";
        return;
    }
    int l1 = 0, r1 = MAX, mid, ans = MAX;
    while (l1 <= r1) {
        mid = (l1 + r1) / 2;
        vector<pii> v;
        v.pub({ -1,-1 });
        int l = max(0, s[1] - mid), r = s[1] + mid;
        for (int i = 1; i < n; ++i) {
            int lx = max(0, s[i] - mid), rx = s[i] + mid;
            if (lx > r + 1) {
                v.pub({ l,r });
                l = lx, r = rx;
            }
            else {
                r = rx;
            }
        }
        v.pub({ l,r });
        if (f[m - 1] > r) {
            l1 = mid + 1;
            continue;
        }
        bool flag = true;
        for (int i = 0; i < (int)v.size() - 1; ++i) {
            int lx = v[i].ss + 1, rx = v[i + 1].ff - 1;
            int ind = upper_bound(all(f), rx) - f.begin() - 1;
            if (ind != -1 && f[ind] >= lx && f[ind] <= rx) {
                flag = false;
                break;
            }
        }
        if (flag) {
            r1 = mid - 1;
            ans = mid;
        }
        else {
            l1 = mid + 1;
        }
    }
    cout << ans << '\n';
    for (int i = 1; i <= n / 3; ++i) {
        cout << "LLR";
    }
}

void cs() {
    int tstc = 1;
    //cin >> tstc;
    while (tstc--) {
        slv();
    }
}

void precalc() {
    return;
}

int main() {
    fastio();
    precalc();
    //precision(0);
    cs();
    return 0;
}

Compilation message

Main.cpp: In function 'll range_sum(ll, ll)':
Main.cpp:97:21: warning: unused variable 'cnt' [-Wunused-variable]
   97 |     ll dif = a - 1, cnt = b - a + 1;
      |                     ^~~
Main.cpp: In function 'll bin_to_dec(std::string)':
Main.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Correct
2	Incorrect	344 KB	User solution is incorrect
3	Halted	0 KB	-

Subtask #1
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	User solution is incorrect
2	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	5 ms	860 KB	Correct
3	Correct	1 ms	344 KB	Correct
4	Correct	14 ms	1252 KB	Correct
5	Correct	14 ms	1112 KB	Correct
6	Correct	0 ms	344 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	13 ms	1116 KB	Correct
9	Correct	16 ms	1256 KB	Correct
10	Correct	14 ms	1116 KB	Correct
11	Correct	9 ms	856 KB	Correct
12	Correct	8 ms	860 KB	Correct
13	Correct	12 ms	1296 KB	Correct
14	Correct	13 ms	1336 KB	Correct
15	Correct	16 ms	1296 KB	Correct
16	Correct	11 ms	1304 KB	Correct