oj.uz

답안 #1039593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039593 2024-07-31T05:02:18 Z 변재우(#10994) Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 105 ms 7260 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010;
int N, M, ans=-1, Nt, Mt, At[Nmax], Bt[Nmax];
pair<int, int> A[Nmax], B[Nmax];
int X[Nmax];
char ret[Nmax];

bool chk(int K, bool op) {
    N=M=0, fill(X+1, X+Mt+1, 0);
    for(int i=1; i<=Nt; i++) {
        if(i>1 && At[i]==At[i-1]) {
            if(i==2 || At[i-1]!=At[i-2]) {
                N--;
                auto p=lower_bound(Bt+1, Bt+Mt+1, At[i]-K);
                auto q=upper_bound(Bt+1, Bt+Mt+1, At[i]+K);
                X[p-Bt]++, X[q-Bt]--;
                ret[i-1]='L', ret[i]='R';
            }
        }
        else A[++N]={At[i], i};
    }
    for(int i=1; i<=Mt; i++) {
        X[i]+=X[i-1];
        if(!X[i]) B[++M]={Bt[i], i};
    }
    string s;
    for(int i=1, j=1; i<=M; i++) {
        bool flag=false;
        while(j<=N && !flag) {
            flag|=(abs(B[i].first-A[j].first)<=K);
            if(flag) {
                if(A[j].first<=B[i].first) {
                    ret[A[j].second]='R';
                    while(i<=M && B[i].first-A[j].first<=K) i++; i--;
                }
                else {
                    ret[A[j].second]='L';
                    while(i<=M && A[j].first-B[i].first>=0) i++; i--;
                }
            }
            j++;
        }
        if(!flag) return false;
    }
    if(op) for(int i=1; i<=Nt; i++) cout<<ret[i];
    return true;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>Nt>>Mt;
    for(int i=1; i<=Nt; i++) cin>>At[i];
    for(int i=1; i<=Mt; i++) cin>>Bt[i];
    fill(ret+1, ret+Nt+1, 'L');
    for(int s=1, e=1e9; s<=e; ) {
        int mid=(s+e)/2;
        if(chk(mid, false)) ans=mid, e=mid-1;
        else s=mid+1;
    }
    if(ans>=0) cout<<ans<<"\n", chk(ans, true);
    else cout<<-1;
    return 0;
}

Compilation message

Main.cpp: In function 'bool chk(long long int, bool)':
Main.cpp:37:21: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   37 |                     while(i<=M && B[i].first-A[j].first<=K) i++; i--;
      |                     ^~~~~
Main.cpp:37:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   37 |                     while(i<=M && B[i].first-A[j].first<=K) i++; i--;
      |                                                                  ^
Main.cpp:41:21: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   41 |                     while(i<=M && A[j].first-B[i].first>=0) i++; i--;
      |                     ^~~~~
Main.cpp:41:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   41 |                     while(i<=M && A[j].first-B[i].first>=0) i++; i--;
      |                                                                  ^

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 10 ms 5468 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 11 ms 4244 KB Correct
5 Correct 12 ms 5888 KB Correct
6 Correct 1 ms 2396 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 3 ms 1116 KB Correct
9 Correct 0 ms 2396 KB Correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 11 ms 4948 KB Correct
3 Correct 8 ms 4696 KB Correct
4 Correct 105 ms 5936 KB Correct
5 Correct 101 ms 7260 KB Correct
6 Correct 0 ms 2396 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 22 ms 4244 KB Correct
9 Correct 30 ms 4160 KB Correct
10 Correct 44 ms 7252 KB Correct
11 Correct 23 ms 6236 KB Correct
12 Correct 48 ms 5980 KB Correct
13 Correct 63 ms 6536 KB Correct
14 Correct 76 ms 6736 KB Correct
15 Correct 85 ms 6996 KB Correct
16 Correct 66 ms 4944 KB Correct

Subtask #3
0.0 / 17.0

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

Subtask #4
0.0 / 27.0

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

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Correct
2 Correct 1 ms 4440 KB Correct
3 Correct 10 ms 5468 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 11 ms 4244 KB Correct
6 Correct 12 ms 5888 KB Correct
7 Correct 1 ms 2396 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 3 ms 1116 KB Correct
10 Correct 0 ms 2396 KB Correct
11 Correct 11 ms 4948 KB Correct
12 Correct 8 ms 4696 KB Correct
13 Correct 105 ms 5936 KB Correct
14 Correct 101 ms 7260 KB Correct
15 Correct 0 ms 2396 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 22 ms 4244 KB Correct
18 Correct 30 ms 4160 KB Correct
19 Correct 44 ms 7252 KB Correct
20 Correct 23 ms 6236 KB Correct
21 Correct 48 ms 5980 KB Correct
22 Correct 63 ms 6536 KB Correct
23 Correct 76 ms 6736 KB Correct
24 Correct 85 ms 6996 KB Correct
25 Correct 66 ms 4944 KB Correct
26 Correct 0 ms 344 KB Correct
27 Correct 0 ms 348 KB Correct
28 Incorrect 0 ms 2396 KB User solution is worse than jury's solution
29 Halted 0 ms 0 KB -