oj.uz

Submission #1046061

# Submission time Handle Problem Language Result Execution time Memory
1046061 2024-08-06T09:32:56 Z dilanyan Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 1300 ms 7056 KB 
//-------------dilanyan------------\\ 
 
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
 
//------------------Kargpefines--------------------\\ 
 
#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
 
void KarginSet(string name = "") {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
 
//-------------------KarginConstants------------------\\ 
 
const ll mod = 1e9 + 7;
const ll inf = 2e9;
 
//-------------------KarginCode-----------------------\\ 
 
const int N = 500005, M = 1000005;

int n, m;

int s[N], f[N];

int tree[4 * N], add[4 * N];

struct segtree {

    int size = 1;

    void init() {
        while (size < m) size <<= 1;
    }

    void push(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        if (tree[x] == 0) {
            tree[2 * x + 1] = tree[2 * x + 2] = 0;
        }
        else if (tree[x] == min(m, rx) - lx) {
            int mid = (lx + rx) / 2;
            tree[2 * x + 1] = min(mid, m) - lx;
            tree[2 * x + 2] = min(rx, m) - min(mid, m);
        }
    }

    void set(int l, int r, int v, int x, int lx, int rx) {
        push(x, lx, rx);
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            tree[x] = v * (rx - lx);
            return;
        }
        int mid = (lx + rx) / 2;
        set(l, r, v, 2 * x + 1, lx, mid);
        set(l, r, v, 2 * x + 2, mid, rx);
        tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }

    void set(int l, int r, int v) {
        set(l, r,v , 0, 0, size);
    }

    int get(int l, int r, int x, int lx, int rx) {
        push(x, lx, rx);
        if (lx >= r || rx <= l) return 0;
        if (lx >= l && rx <= r) return tree[x];
        int mid = (lx + rx) / 2;
        int getl = get(l, r, 2 * x + 1, lx, mid),
            getr = get(l, r, 2 * x + 2, mid, rx);
        return getl + getr;
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, size);
    }

};

void KarginSolve() {
    cin >> n >> m;
    for (int i = 0;i < n;i++) cin >> s[i];
    for (int i = 0;i < m;i++) cin >> f[i];
    ll l = 0, r = 1e9, ans = -1;
    segtree st;
    st.init();
    while (l <= r) {
        ll mid = (l + r) / 2;
        st.set(0, m, 0);
        for (int i = 0;i < n;i++) {
            int sp = lower(f, f + m, s[i] - mid) - f;
            int ep = upper(f, f + m, s[i]) - f;
            if (st.get(sp, ep) != ep - sp) {
                st.set(sp, ep, 1);
            }
            else {
                sp = lower(f, f + m, s[i]) - f;
                ep = upper(f, f + m, s[i] + mid) - f;
                st.set(sp, ep, 1);
            }
        }
        if (tree[0] == m) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    if (ans == -1) cout << -1 << '\n';
    else {
        cout << ans << '\n';
        st.set(0, m, 0);
        for (int i = 0;i < n;i++) {
            int sp = lower(f, f + m, s[i] - ans) - f;
            int ep = upper(f, f + m, s[i]) - f;
            if (st.get(sp, ep) != ep - sp) {
                st.set(sp, ep, 1);
                cout << 'L';
            }
            else {
                sp = lower(f, f + m, s[i]) - f;
                ep = upper(f, f + m, s[i] + ans) - f;
                st.set(sp, ep, 1);
                cout << 'R';
            }
        }
        cout << '\n';
    }
}

int main() {
    KarginSet();
    int test = 1;
    //cin >> test;
    while (test--) {
        KarginSolve();
    }
    return 0;
}

Compilation message

Main.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //-------------dilanyan------------\\
      | ^
Main.cpp:8:1: warning: multi-line comment [-Wcomment]
    8 | //------------------Kargpefines--------------------\\
      | ^
Main.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | //-------------------KarginConstants------------------\\
      | ^
Main.cpp:32:1: warning: multi-line comment [-Wcomment]
   32 | //-------------------KarginCode-----------------------\\
      | ^
Main.cpp: In function 'void KarginSet(std::string)':
Main.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4444 KB Correct
2 Correct 5 ms 6492 KB Correct
3 Incorrect 0 ms 4440 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 1 ms 4444 KB Correct
2 Correct 23 ms 7056 KB Correct
3 Correct 86 ms 4444 KB Correct
4 Correct 1281 ms 7056 KB Correct
5 Correct 1209 ms 6992 KB Correct
6 Correct 1 ms 6492 KB Correct
7 Correct 0 ms 4444 KB Correct
8 Correct 1253 ms 7040 KB Correct
9 Correct 1297 ms 6960 KB Correct
10 Correct 1300 ms 6992 KB Correct
11 Correct 307 ms 4556 KB Correct
12 Correct 494 ms 7000 KB Correct
13 Correct 1178 ms 6992 KB Correct
14 Correct 1157 ms 6992 KB Correct
15 Correct 1101 ms 6996 KB Correct
16 Correct 1215 ms 6800 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 0 ms 4444 KB Correct
3 Incorrect 1 ms 4444 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 1 ms 4444 KB Correct
2 Incorrect 140 ms 7004 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 1 ms 4444 KB Correct
2 Correct 0 ms 4444 KB Correct
3 Correct 5 ms 6492 KB Correct
4 Incorrect 0 ms 4440 KB User solution is worse than jury's solution
5 Halted 0 ms 0 KB -