oj.uz

Submission #1046064

# Submission time Handle Problem Language Result Execution time Memory
1046064 2024-08-06T09:35:44 Z dilanyan Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 1304 ms 7084 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);
        assert(tree[0] == 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 6 ms 6488 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 22 ms 7084 KB Correct
3 Correct 89 ms 4592 KB Correct
4 Correct 1196 ms 6996 KB Correct
5 Correct 1180 ms 7000 KB Correct
6 Correct 1 ms 6492 KB Correct
7 Correct 0 ms 4444 KB Correct
8 Correct 1261 ms 6960 KB Correct
9 Correct 1304 ms 6960 KB Correct
10 Correct 1225 ms 6948 KB Correct
11 Correct 294 ms 4444 KB Correct
12 Correct 489 ms 7000 KB Correct
13 Correct 1148 ms 6928 KB Correct
14 Correct 1150 ms 7040 KB Correct
15 Correct 1064 ms 6924 KB Correct
16 Correct 1220 ms 6928 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 136 ms 7000 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 6 ms 6488 KB Correct
4 Incorrect 0 ms 4440 KB User solution is worse than jury's solution
5 Halted 0 ms 0 KB -