oj.uz

Submission #1039559

# Submission time Handle Problem Language Result Execution time Memory
1039559 2024-07-31T04:34:13 Z 변재우(#10994) Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 19 ms 5332 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(A[j]<=B[i]) {
                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+Mt+1, 'L');
    for(int s=0, e=1e9; s<=e; ) {
        int mid=(s+e)/2;
        if(chk(mid, false)) ans=mid, e=mid-1;
        else s=mid+1;
    }
    cout<<ans<<"\n";
    if(ans>=0) chk(ans, true);
    return 0;
}

Compilation message

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

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 19 ms 5036 KB Correct
3 Correct 1 ms 4444 KB Correct
4 Correct 12 ms 5256 KB Correct
5 Correct 13 ms 5212 KB Correct
6 Correct 1 ms 4444 KB Correct
7 Correct 1 ms 4444 KB Correct
8 Correct 4 ms 4568 KB Correct
9 Correct 1 ms 4444 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 12 ms 5212 KB Correct
3 Incorrect 10 ms 4700 KB Invalid character in the string
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4444 KB Correct
3 Incorrect 1 ms 4456 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Incorrect 15 ms 5332 KB User solution is incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4444 KB Correct
3 Correct 19 ms 5036 KB Correct
4 Correct 1 ms 4444 KB Correct
5 Correct 12 ms 5256 KB Correct
6 Correct 13 ms 5212 KB Correct
7 Correct 1 ms 4444 KB Correct
8 Correct 1 ms 4444 KB Correct
9 Correct 4 ms 4568 KB Correct
10 Correct 1 ms 4444 KB Correct
11 Correct 12 ms 5212 KB Correct
12 Incorrect 10 ms 4700 KB Invalid character in the string
13 Halted 0 ms 0 KB -