oj.uz

Submission #1039599

# Submission time Handle Problem Language Result Execution time Memory
1039599 2024-07-31T05:13:12 Z 김은성(#10990) Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;
int s[100009], f[100009];
bool ch[100009];
int main(){
    int n, m, i, j, k;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
        scanf("%d", &s[i]);
    for(i=1; i<=m; i++)
        scanf("%d", &f[i]);
    int lo = 0, hi = 1000000009, mid;
    while(lo < hi){
        mid = (lo+hi)/2;
        int pos = -1;
        for(i=0; i<(1<<n); i++){
            for(j=1; j<=m; j++)
                ch[j] = 0;
            for(j=0; j<n; j++){
                for(k=1; k<=m; k++){
                    if((i & (1<<j)) && f[k] >= s[j+1]-mid && f[k] <= s[j+1])
                        ch[k] = 1;
                    if(!(i&(1<<j)) && f[k] <= s[j+1]+mid && f[k] >= s[j+1])
                        ch[k] = 1;
                }
            }
            bool flag = 0;
            for(j=1; j<=m; j++){
                if(!ch[j])
                    flag = 1;
            }
            if(!flag){
                pos = i;
                break;
            }
        }
        if(pos == -1)
            lo = mid+1;
        else
            hi = mid;
    }
    mid = lo;
    int pos = -1;
    for(i=0; i<(1<<n); i++){
        for(j=1; j<=m; j++)
            ch[j] = 0;
        for(j=0; j<n; j++){
            for(k=1; k<=m; k++){
                if((i & (1<<j)) && f[k] >= s[j+1]-mid && f[k] <= s[j+1])
                    ch[k] = 1;
                if(!(i&(1<<j)) && f[k] <= s[j+1]+mid && f[k] >= s[j+1])
                    ch[k] = 1;
            }
        }
        bool flag = 0;
        for(j=1; j<=m; j++){
            if(!ch[j])
                flag = 1;
        }
        if(!flag){
            pos = i;
            break;
        }
    }
    if(pos == -1)
        printf("-1\n");
    else{
        printf("%d\n", mid);
        for(i=0; i<n; i++)
            printf("%c", (pos & (1<<i)) ? 'L' : 'R');
        printf("\n");
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         scanf("%d", &s[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf("%d", &f[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 1 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 13 ms 856 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 15 ms 860 KB Correct
5 Correct 16 ms 860 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 3 ms 348 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 2055 ms 860 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 1 ms 348 KB Correct
3 Correct 64 ms 348 KB Correct
4 Correct 5 ms 344 KB Correct
5 Correct 166 ms 428 KB Correct
6 Correct 115 ms 344 KB Correct
7 Correct 2 ms 348 KB Correct
8 Correct 128 ms 424 KB Correct
9 Correct 175 ms 348 KB Correct
10 Correct 221 ms 348 KB Correct
11 Correct 20 ms 344 KB Correct
12 Correct 201 ms 440 KB Correct
13 Correct 121 ms 432 KB Correct
14 Correct 11 ms 348 KB Correct
15 Correct 34 ms 344 KB Correct
16 Correct 47 ms 348 KB Correct
17 Correct 61 ms 452 KB Correct
18 Correct 13 ms 348 KB Correct
19 Correct 1 ms 348 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 2085 ms 756 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 1 ms 348 KB Correct
3 Correct 13 ms 856 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 15 ms 860 KB Correct
6 Correct 16 ms 860 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 3 ms 348 KB Correct
10 Correct 0 ms 348 KB Correct
11 Execution timed out 2055 ms 860 KB Time limit exceeded
12 Halted 0 ms 0 KB -