oj.uz

답안 #1069935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069935 2024-08-22T10:14:30 Z Alebn Sprinklers (CEOI24_sprinklers) C++14
20 / 100
 2000 ms 5068 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

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 18 ms 5068 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 24 ms 4816 KB Correct
5 Correct 23 ms 3536 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 5 ms 1112 KB Correct
9 Correct 1 ms 344 KB Correct

Subtask #2
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Execution timed out 2039 ms 3532 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 103 ms 344 KB Correct
4 Correct 9 ms 476 KB Correct
5 Correct 218 ms 476 KB Correct
6 Correct 196 ms 348 KB Correct
7 Correct 2 ms 344 KB Correct
8 Correct 173 ms 484 KB Correct
9 Correct 194 ms 344 KB Correct
10 Correct 261 ms 348 KB Correct
11 Correct 36 ms 344 KB Correct
12 Correct 192 ms 480 KB Correct
13 Correct 179 ms 348 KB Correct
14 Correct 14 ms 348 KB Correct
15 Correct 17 ms 504 KB Correct
16 Correct 46 ms 344 KB Correct
17 Correct 32 ms 348 KB Correct
18 Correct 24 ms 344 KB Correct
19 Correct 1 ms 348 KB Correct
20 Correct 1 ms 348 KB Correct

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Execution timed out 2066 ms 3536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 18 ms 5068 KB Correct
4 Correct 0 ms 344 KB Correct
5 Correct 24 ms 4816 KB Correct
6 Correct 23 ms 3536 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 5 ms 1112 KB Correct
10 Correct 1 ms 344 KB Correct
11 Execution timed out 2039 ms 3532 KB Time limit exceeded
12 Halted 0 ms 0 KB -