oj.uz

Submission #1046090

# Submission time Handle Problem Language Result Execution time Memory
1046090 2024-08-06T09:57:53 Z dilanyan Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 1380 ms 2396 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 = 100005, 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) - min(lx, m)) {
            int mid = (lx + rx) / 2;
            tree[2 * x + 1] = min(mid, m) - min(lx, m);
            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 && f[sp] != s[i]) {
                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 && f[sp] != s[i]) {
                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 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 5 ms 856 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 6 ms 860 KB Correct
5 Correct 6 ms 1112 KB Correct
6 Correct 0 ms 2392 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 604 KB Correct
9 Correct 0 ms 344 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 22 ms 1672 KB Correct
3 Correct 101 ms 348 KB Correct
4 Correct 1232 ms 2028 KB Correct
5 Correct 1266 ms 2132 KB Correct
6 Correct 1 ms 2396 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1339 ms 1948 KB Correct
9 Correct 1380 ms 1868 KB Correct
10 Correct 1249 ms 1872 KB Correct
11 Correct 330 ms 860 KB Correct
12 Correct 551 ms 1876 KB Correct
13 Correct 1280 ms 1640 KB Correct
14 Correct 1233 ms 1644 KB Correct
15 Correct 1132 ms 1764 KB Correct
16 Correct 1221 ms 1872 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Incorrect 0 ms 348 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 0 ms 344 KB Correct
2 Incorrect 141 ms 1628 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 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 5 ms 856 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 6 ms 860 KB Correct
6 Correct 6 ms 1112 KB Correct
7 Correct 0 ms 2392 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 1 ms 604 KB Correct
10 Correct 0 ms 344 KB Correct
11 Correct 22 ms 1672 KB Correct
12 Correct 101 ms 348 KB Correct
13 Correct 1232 ms 2028 KB Correct
14 Correct 1266 ms 2132 KB Correct
15 Correct 1 ms 2396 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 1339 ms 1948 KB Correct
18 Correct 1380 ms 1868 KB Correct
19 Correct 1249 ms 1872 KB Correct
20 Correct 330 ms 860 KB Correct
21 Correct 551 ms 1876 KB Correct
22 Correct 1280 ms 1640 KB Correct
23 Correct 1233 ms 1644 KB Correct
24 Correct 1132 ms 1764 KB Correct
25 Correct 1221 ms 1872 KB Correct
26 Incorrect 0 ms 348 KB User solution is worse than jury's solution
27 Halted 0 ms 0 KB -