Submission #1039764

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039764	2024-07-31T08:35:59 Z	변재우(#10994)	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	100 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(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(B[i].first<=A[r].first+K) i++; i--;
      |         ^~~~~
Main.cpp:59:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   59 |         while(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	0 ms	4444 KB	Correct

Subtask #1
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4444 KB	Correct
2	Runtime error	11 ms	9816 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	17 ms	5164 KB	Correct
3	Correct	8 ms	4700 KB	Correct
4	Correct	100 ms	6024 KB	Correct
5	Correct	98 ms	4664 KB	Correct
6	Correct	1 ms	2396 KB	Correct
7	Correct	0 ms	2396 KB	Correct
8	Correct	23 ms	5912 KB	Correct
9	Correct	35 ms	5976 KB	Correct
10	Correct	50 ms	6024 KB	Correct
11	Correct	26 ms	5456 KB	Correct
12	Correct	49 ms	5392 KB	Correct
13	Correct	68 ms	5776 KB	Correct
14	Correct	75 ms	2396 KB	Correct
15	Correct	78 ms	5720 KB	Correct
16	Correct	60 ms	5720 KB	Correct