oj.uz

답안 #1046085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046085 2024-08-06T09:51:27 Z dilanyan Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 1312 ms 2392 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) - 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 && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 5 ms 840 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 5 ms 860 KB Correct
5 Correct 7 ms 860 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 348 KB Correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 24 ms 1628 KB Correct
3 Correct 89 ms 572 KB Correct
4 Correct 1181 ms 2028 KB Correct
5 Correct 1240 ms 2024 KB Correct
6 Correct 1 ms 2392 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1230 ms 1856 KB Correct
9 Correct 1312 ms 1872 KB Correct
10 Correct 1261 ms 1876 KB Correct
11 Correct 300 ms 864 KB Correct
12 Correct 499 ms 1684 KB Correct
13 Correct 1174 ms 1620 KB Correct
14 Correct 1150 ms 1620 KB Correct
15 Correct 1072 ms 1644 KB Correct
16 Correct 1175 ms 1616 KB Correct

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Incorrect 1 ms 344 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Incorrect 138 ms 1624 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 5 ms 840 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 5 ms 860 KB Correct
6 Correct 7 ms 860 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 348 KB Correct
11 Correct 24 ms 1628 KB Correct
12 Correct 89 ms 572 KB Correct
13 Correct 1181 ms 2028 KB Correct
14 Correct 1240 ms 2024 KB Correct
15 Correct 1 ms 2392 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 1230 ms 1856 KB Correct
18 Correct 1312 ms 1872 KB Correct
19 Correct 1261 ms 1876 KB Correct
20 Correct 300 ms 864 KB Correct
21 Correct 499 ms 1684 KB Correct
22 Correct 1174 ms 1620 KB Correct
23 Correct 1150 ms 1620 KB Correct
24 Correct 1072 ms 1644 KB Correct
25 Correct 1175 ms 1616 KB Correct
26 Incorrect 1 ms 344 KB User solution is worse than jury's solution
27 Halted 0 ms 0 KB -