oj.uz

답안 #1039694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039694 2024-07-31T07:44:52 Z 정지훈(#11027) Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 75 ms 6732 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100000];
int b[100000];
int pos[100000];
typedef pair<int,int> P;
int dp[100000][3];
int k;

int getpr(int bi) {
    int ai=lower_bound(a,a+n,b[bi])-a;
    return ai-1;
}

int ans(int ind,int t) {
if (ind==m) return 1;
    if (dp[ind][t]!=-1) {
        return dp[ind][t];
    }
    int in=upper_bound(a,a+n,b[ind])-a;
    int ret=0;
    if (t==0) {
        if (in>0&&a[in-1]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-1]+k)-b;
            return dp[ind][t]=ans(ni,0);
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                ret|=ans(ni,0);
            }
            else {
                ret|=ans(ni,1);
            }
            ret|=ans(ind,2);
return dp[ind][t]=ret;
        }
        else {
            return dp[ind][t]=0;
        }
    }
    if (t==1) {
        if (in>1&&a[in-2]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-2]+k)-b;
            return dp[ind][t]=ans(ni,0);
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                ret|=ans(ni,0);
            }
            else {
                ret|=ans(ni,1);
            }
            ret|=ans(ind,2);
        }
        else {
            return dp[ind][t]=0;
        }
        return dp[ind][t]=ret;
    }
    if (t==2) {
        if (in<n-1&&a[in+1]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in]+k)-b;
            if (getpr(ni)!=in+1) {
                ret|=ans(ni,0);
            }
            else {
                ret|=ans(ni,1);
            }
            return dp[ind][t]=ret;
        }
        else {
            return dp[ind][t]=0;
        }
    }
}

void track(int ind,int t) {
if (ind==m) return;
    int in=upper_bound(a,a+n,b[ind])-a;
    int ret=0;
    if (t==0) {
        if (in>0&&a[in-1]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-1]+k)-b;
            pos[in-1]=1;
            track(ni,0);
            return;
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                if (ans(ni,0)) {
                    pos[in]=0;
                    track(ni,0);
                    return;
                }
                ret|=ans(ni,0);
            }
            else {
                if (ans(ni,1)) {
                    pos[in]=0;
                    track(ni,1);
                    return;
                }
                ret|=ans(ni,1);
            }
                if (ans(ind,2)) {
                    pos[in]=1;
                    track(ind,2);
                    return;
                }
            ret|=ans(ind,2);
        }
        else {
            return;
        }
    }
    if (t==1) {
        if (in>1&&a[in-2]>=b[ind]-k) {
            int ni=upper_bound(b,b+m,a[in-2]+k)-b;
pos[in-2]=1;
            track(ni,0);
            return;
        }
        else if (in!=n&&a[in]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in])-b;
            if (getpr(ni)!=in) {
                if (ans(ni,0)) {
                    pos[in]=0;
                    track(ni,0);
                    return;
                }
            }
            else {
                if (ans(ni,1)) {
                    pos[in]=0;
                    track(ni,1);
                    return;
                }
            }
                if (ans(ind,2)) {
                    pos[in]=1;
                    track(ind,2);
                    return;
                }
        }
        else {
            return;
        }
    }
    if (t==2) {
        if (in<n-1&&a[in+1]<=b[ind]+k) {
            int ni=upper_bound(b,b+m,a[in]+k)-b;
            if (getpr(ni)!=in+1) {
                if (ans(ni,0)) {
                    pos[in+1]=0;
                    track(ni,0);
                    return;
                }
            }
            else {
                if (ans(ni,1)) {
                    pos[in+1]=0;
                    track(ni,1);
                    return;
                }
            }
            return;
        }
        else {
            return;
        }
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++) {
        scanf("%d",&b[i]);
    }
    int lo=-1; //impossible
    int hi=1e9+7; //possible
    if (n==1) {
        int f=-1;
        for(int i=0;i<m;i++) {
            if (b[i]<a[0]) {
                if (f==1) {
                    f=2;
                    break;
                }
                f=0;
            }
            if (b[i]>a[0]) {
                if (f==0) {
                    f=2;
                    break;
                }
                f=1;
            }
        }
        if (f==2) {
            printf("-1");
            return 0;
        }
    }
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        memset(dp,-1,sizeof(dp));
        k=mid;
        if (ans(0,0)) {
            hi=mid;
        }
        else {
            lo=mid;
        }
    }
    k=hi;
memset(dp,-1,sizeof(dp));
    ans(0,0);
    track(0,0);
    printf("%d\n",hi);
    for(int i=0;i<n;i++) {
        printf("%c",pos[i]?'R':'L');
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int ans(int, int)':
Main.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
   79 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         scanf("%d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 440 KB Correct
2 Correct 8 ms 2652 KB Correct
3 Correct 2 ms 1628 KB Correct
4 Correct 8 ms 1628 KB Correct
5 Correct 8 ms 1852 KB Correct
6 Correct 2 ms 2652 KB Correct
7 Correct 1 ms 1628 KB Correct
8 Correct 2 ms 604 KB Correct
9 Correct 1 ms 1628 KB Correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 12 ms 2876 KB Correct
3 Correct 5 ms 2904 KB Correct
4 Correct 35 ms 5276 KB Correct
5 Correct 42 ms 5212 KB Correct
6 Correct 2 ms 1624 KB Correct
7 Correct 1 ms 2652 KB Correct
8 Correct 19 ms 4428 KB Correct
9 Correct 20 ms 4432 KB Correct
10 Correct 19 ms 4288 KB Correct
11 Correct 12 ms 3676 KB Correct
12 Correct 19 ms 3660 KB Correct
13 Correct 43 ms 5972 KB Correct
14 Correct 57 ms 6512 KB Correct
15 Correct 75 ms 6732 KB Correct
16 Correct 30 ms 5724 KB Correct

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 0 ms 440 KB Correct
3 Incorrect 2 ms 1624 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Correct
2 Incorrect 23 ms 3376 KB User solution is incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Correct
2 Correct 0 ms 440 KB Correct
3 Correct 8 ms 2652 KB Correct
4 Correct 2 ms 1628 KB Correct
5 Correct 8 ms 1628 KB Correct
6 Correct 8 ms 1852 KB Correct
7 Correct 2 ms 2652 KB Correct
8 Correct 1 ms 1628 KB Correct
9 Correct 2 ms 604 KB Correct
10 Correct 1 ms 1628 KB Correct
11 Correct 12 ms 2876 KB Correct
12 Correct 5 ms 2904 KB Correct
13 Correct 35 ms 5276 KB Correct
14 Correct 42 ms 5212 KB Correct
15 Correct 2 ms 1624 KB Correct
16 Correct 1 ms 2652 KB Correct
17 Correct 19 ms 4428 KB Correct
18 Correct 20 ms 4432 KB Correct
19 Correct 19 ms 4288 KB Correct
20 Correct 12 ms 3676 KB Correct
21 Correct 19 ms 3660 KB Correct
22 Correct 43 ms 5972 KB Correct
23 Correct 57 ms 6512 KB Correct
24 Correct 75 ms 6732 KB Correct
25 Correct 30 ms 5724 KB Correct
26 Incorrect 2 ms 1624 KB User solution is incorrect
27 Halted 0 ms 0 KB -