Submission #1046160

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046160	2024-08-06T10:47:36 Z	c2zi6	Sprinklers (CEOI24_sprinklers)	C++14	6 / 100	38 ms	2252 KB

Main

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<bool> VB;
typedef vector<VB> VVB;
 
bool checkcover(VI& a, VPI& ranges) {
    /* khamarem or erkusn el sortavorac en*/
    int i = 0;
    for (auto[L, R] : ranges) {
        if (a[i] < L) return false;
        while (i < a.size() && a[i] <= R) i++;
        if (i == a.size()) break;
    }
    return i == a.size();
}

void solve() {
    int n, m;
    cin >> n >> m;
    VI a(n);
    /* jur */
    VI b(m);
    /* caxik */
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    
    string ans(n, 'R');
    for (int i = 0; i < a.size(); i += 3) ans[i] = 'L';
    auto can = [&](ll d) {
        VPI ranges;
        for (int i = 0; i < a.size(); i += 3) {
            ranges.pb({a[i]-d, a[i]+d});
        }
        return checkcover(b, ranges);
    };

        /*replr(i, 0, 10) cout << can(i) << endl;*/

    ll l = -1, r = 2e9;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (can(m)) r = m;
        else l = m;
    }
    if (r == 2e9) cout << -1 << endl;
    else {
        can(r);
        cout << r << endl;
        cout << ans << endl;
    }
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	/*freopen("mincross.in", "r", stdin); */
	/*freopen("test.out", "w", stdout); */
	int t = 1;
	/*cin >> t; */
	while (t--) solve();
}

Compilation message

Main.cpp: In function 'bool checkcover(VI&, VPI&)':
Main.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto[L, R] : ranges) {
      |              ^
Main.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while (i < a.size() && a[i] <= R) i++;
      |                ~~^~~~~~~~~~
Main.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (i == a.size()) break;
      |             ~~^~~~~~~~~~~
Main.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     return i == a.size();
      |            ~~^~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < a.size(); i += 3) ans[i] = 'L';
      |                     ~~^~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int i = 0; i < a.size(); i += 3) {
      |                         ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Correct
2	Incorrect	348 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	348 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	348 KB	Correct
2	Correct	7 ms	860 KB	Correct
3	Correct	2 ms	344 KB	Correct
4	Correct	34 ms	2192 KB	Correct
5	Correct	31 ms	2124 KB	Correct
6	Correct	0 ms	600 KB	Correct
7	Correct	1 ms	348 KB	Correct
8	Correct	29 ms	2252 KB	Correct
9	Correct	23 ms	2120 KB	Correct
10	Correct	24 ms	2208 KB	Correct
11	Correct	22 ms	1732 KB	Correct
12	Correct	14 ms	1224 KB	Correct
13	Correct	35 ms	1996 KB	Correct
14	Correct	24 ms	1996 KB	Correct
15	Correct	38 ms	2056 KB	Correct
16	Correct	27 ms	2064 KB	Correct