oj.uz

Submission #1070051

# Submission time Handle Problem Language Result Execution time Memory
1070051 2024-08-22T11:19:10 Z vjudge1 Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 4816 KB 
#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
struct Obj {
    int t, pos, i;
    Obj(){}
    Obj(int ti, int pi, int ii):t(ti),pos(pi),i(ii){}
};
bitset<20> bs;
bool trywith(vector<Obj>& a, int& n, int K) {
    bool ok;
    for(int i = 0; i < (1 << n); i++) {
        ok = true;
        bitset<20> bit(i);
        vector<bool> oki(a.size(), false);
        for(int j = 0; j < a.size(); j++) {
            if(!a[j].t) {
                oki[j] = true;
                for(int k = 0; k < a.size(); k++) {
                    if(bit[a[j].i] && a[j].pos <= a[k].pos && a[k].pos <= a[j].pos + K || !bit[a[j].i] && a[j].pos - K <= a[k].pos && a[k].pos <= a[j].pos) oki[k] = true;
                }
            }
        }
        for(int j = 0; j < a.size(); j++) {
            if(!oki[j]) ok = false;
        }
        if(ok) {
            bs = bit;
            break;
        }
    }
    return ok;
}
 
void solve() {
    int n, m, temp;
    cin >> n >> m;
    vector<Obj> a;
    for(int i = 0; i < n; i++) {
        cin >> temp;
        a.push_back(Obj(0, temp, i));
    }
    for(int i = 0; i < m; i++) {
        cin >> temp;
        a.push_back(Obj(1, temp, i));
    }
    sort(a.begin(), a.end(), [](Obj x, Obj y){
        if(x.pos == y.pos) return x.t > y.t;
        return x.pos < y.pos;
    });
    int l = 0, r = 1e9+1, mid, ans = -1;
    while(l <= r) {
        mid = (l + r) / 2;
        if(trywith(a, n, mid)) {
            r = mid - 1;
            ans = mid;
        } else l = mid + 1;
    }
    cout << ans << "\n";
    if(ans != -1) {
        for(int i = 0; i < n; i++) {
            if(bs[i]) cout << 'R';
            else cout << 'L';
        }
        cout << "\n";
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message

Main.cpp: In function 'bool trywith(std::vector<Obj>&, long long int&, long long int)':
Main.cpp:18:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int j = 0; j < a.size(); j++) {
      |                        ~~^~~~~~~~~~
Main.cpp:21:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                 for(int k = 0; k < a.size(); k++) {
      |                                ~~^~~~~~~~~~
Main.cpp:22:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |                     if(bit[a[j].i] && a[j].pos <= a[k].pos && a[k].pos <= a[j].pos + K || !bit[a[j].i] && a[j].pos - K <= a[k].pos && a[k].pos <= a[j].pos) oki[k] = true;
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j = 0; j < a.size(); j++) {
      |                        ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 16 ms 4560 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 24 ms 3536 KB Correct
5 Correct 23 ms 3536 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 4 ms 1368 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Execution timed out 2047 ms 4816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 103 ms 348 KB Correct
4 Correct 9 ms 348 KB Correct
5 Correct 214 ms 348 KB Correct
6 Correct 193 ms 348 KB Correct
7 Correct 3 ms 348 KB Correct
8 Correct 173 ms 484 KB Correct
9 Correct 198 ms 348 KB Correct
10 Correct 265 ms 476 KB Correct
11 Correct 36 ms 600 KB Correct
12 Correct 199 ms 344 KB Correct
13 Correct 197 ms 344 KB Correct
14 Correct 16 ms 344 KB Correct
15 Correct 15 ms 348 KB Correct
16 Correct 45 ms 348 KB Correct
17 Correct 31 ms 348 KB Correct
18 Correct 25 ms 344 KB Correct
19 Correct 1 ms 344 KB Correct
20 Correct 1 ms 348 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Execution timed out 2070 ms 4816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 16 ms 4560 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 24 ms 3536 KB Correct
6 Correct 23 ms 3536 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 4 ms 1368 KB Correct
10 Correct 0 ms 348 KB Correct
11 Execution timed out 2047 ms 4816 KB Time limit exceeded
12 Halted 0 ms 0 KB -