Submission #1039762

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039762	2024-07-31T08:34:58 Z	변재우(#10994)	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	135 ms	11356 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(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(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(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(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(B[i].first<=A[j].first+K) i++; i--;
      |             ^~~~~
Main.cpp:32:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   32 |             while(B[i].first<=A[j].first+K) i++; i--;
      |                                                  ^
Main.cpp:40:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   40 |             while(B[i].first<=A[j].first) i++; i--;
      |             ^~~~~
Main.cpp:40:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   40 |             while(B[i].first<=A[j].first) i++; i--;
      |                                                ^
Main.cpp:48:17: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   48 |                 while(B[i].first<=A[l].first+K) i++; i--;
      |                 ^~~~~
Main.cpp:48:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   48 |                 while(B[i].first<=A[l].first+K) i++; i--;
      |                                                      ^
Main.cpp:53:17: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   53 |                 while(B[i].first<=A[r].first+K) i++; i--;
      |                 ^~~~~
Main.cpp:53:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   53 |                 while(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	4560 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	10588 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	4560 KB	Correct
2	Correct	12 ms	5980 KB	Correct
3	Correct	8 ms	4700 KB	Correct
4	Correct	100 ms	4848 KB	Correct
5	Correct	135 ms	4688 KB	Correct
6	Correct	0 ms	344 KB	Correct
7	Correct	1 ms	2396 KB	Correct
8	Correct	25 ms	7916 KB	Correct
9	Correct	58 ms	8004 KB	Correct
10	Correct	72 ms	8020 KB	Correct
11	Correct	30 ms	6384 KB	Correct
12	Correct	53 ms	6632 KB	Correct
13	Correct	72 ms	6828 KB	Correct
14	Correct	83 ms	7044 KB	Correct
15	Correct	78 ms	7248 KB	Correct
16	Correct	70 ms	6748 KB	Correct