제출 #1346578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1346578		MrAndria	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2093 ms	2232 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
int n,m,x,curr,ans,a[1000005],b[1000005];
signed main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        
    }
    int idx=0;
    ans=INT_MAX;
    for(int mask=0;mask<(1<<n);mask++){
        int l=0;
        int r=1e9;
        int curr_ans=INT_MAX;
        while(l<=r){
            int k=(l+r)/2;
            vector <pair <int,int> > vec;
            for(int i=0;i<n;i++){
                if(mask&(1<<i)){
                    vec.pb(make_pair(a[i],1));
                    vec.pb(make_pair(a[i]+k+1,-1));
                }else{
                    vec.pb(make_pair(a[i]+1,-1));
                    vec.pb(make_pair(a[i]-k,+1));
                    
                }
            }
            sort(vec.begin(),vec.end());
            vec.pb(make_pair(INT_MAX,-1));
            curr=0;
            int sum=0;
            bool b1=0;
            for(int i=1;i<=m;i++){
                while(vec[curr].ff<=b[i]){
                    sum+=vec[curr].ss;
                    curr++;
                }
                if(sum==0){
                    b1=1;
                    break;
                }

            }
            if(b1){
                l=k+1;
            }else{
                curr_ans=k;
                r=k-1;
            }



        }
        ans=min(ans,curr_ans);
        if(ans==curr_ans){
            idx=mask;
        }
    }
    if(ans==INT_MAX){
        cout<<"-1"<<endl;
    }else{
        cout<<ans<<endl;
        for(int i=0;i<n;i++){
            if(idx&(1<<i)){
                cout<<"R";
            }else{
                cout<<"L";
            }
        }
    }
    cout<<endl;

}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 17 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47