Submission #1039765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039765	2024-07-31T08:37:04 Z	변재우(#10994)	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	102 ms	10332 KB

Main

#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};
    }
    for(int i=1, j=1; i<=M; i++) {
        if(j>N) return false;
        if(A[j].first<=B[i].first) {
            while(i<=M && B[i].first<=A[j].first+K) i++; i--;
            ret[A[j].first]='R';
            j++; continue;
        }
        int l=j, r=j;
        while(r<N && A[r+1].first<=B[i].first+K) ++r;
        if(A[l].first>B[i].first+K) return false;
        if(r-l+1==1) {
            while(i<=M && B[i].first<=A[j].first) i++; i--;
            ret[A[j].first]='L';
            j++;
            continue;
        }
        if(r-l+1==2) {
            auto p=upper_bound(B+1, B+M+1, make_pair(A[l].first, (int)INT_MAX));
            if(p<=B+M && (*p).first<A[r].first) {
                while(i<=M && B[i].first<=A[l].first+K) i++; i--;
                ret[A[j].first]='R', ret[A[j+1].first]='L';
                j+=2; continue;
            }
            else {
                while(i<=M && B[i].first<=A[r].first+K) i++; i--;
                ret[A[j].first]='L', ret[A[j+1].first]='R';
                j+=2; continue;
            }
        }
        ret[A[l].first]='R', ret[A[l+1].first]='L', ret[A[r].first]='R';
        while(i<=M && B[i].first<=A[r].first+K) i++; i--;
        j=r+1;
    }
    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=0, 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:32:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   32 |             while(i<=M && B[i].first<=A[j].first+K) i++; i--;
      |             ^~~~~
Main.cpp:32:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   32 |             while(i<=M && B[i].first<=A[j].first+K) i++; i--;
      |                                                          ^
Main.cpp:40:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   40 |             while(i<=M && B[i].first<=A[j].first) i++; i--;
      |             ^~~~~
Main.cpp:40:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   40 |             while(i<=M && B[i].first<=A[j].first) i++; i--;
      |                                                        ^
Main.cpp:48:17: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   48 |                 while(i<=M && B[i].first<=A[l].first+K) i++; i--;
      |                 ^~~~~
Main.cpp:48:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   48 |                 while(i<=M && B[i].first<=A[l].first+K) i++; i--;
      |                                                              ^
Main.cpp:53:17: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   53 |                 while(i<=M && B[i].first<=A[r].first+K) i++; i--;
      |                 ^~~~~
Main.cpp:53:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   53 |                 while(i<=M && B[i].first<=A[r].first+K) i++; i--;
      |                                                              ^
Main.cpp:59:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   59 |         while(i<=M && B[i].first<=A[r].first+K) i++; i--;
      |         ^~~~~
Main.cpp:59:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   59 |         while(i<=M && B[i].first<=A[r].first+K) 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
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Correct
2	Runtime error	10 ms	9820 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Correct
2	Correct	13 ms	4956 KB	Correct
3	Correct	8 ms	4952 KB	Correct
4	Correct	102 ms	5980 KB	Correct
5	Correct	102 ms	5976 KB	Correct
6	Correct	1 ms	4444 KB	Correct
7	Correct	1 ms	4444 KB	Correct
8	Correct	23 ms	6032 KB	Correct
9	Correct	34 ms	6104 KB	Correct
10	Correct	46 ms	5976 KB	Correct
11	Correct	23 ms	5468 KB	Correct
12	Correct	51 ms	5212 KB	Correct
13	Correct	67 ms	5724 KB	Correct
14	Correct	81 ms	5760 KB	Correct
15	Correct	81 ms	5768 KB	Correct
16	Correct	66 ms	5776 KB	Correct